Составьте таблицу истинности для выражения x y. III. Объяснение нового материала

Продолжительность урока: 45 мин

Тип урока: комбинированный:

• проверка знаний – устная работа;
• новый материал – лекция;
• закрепление – практические упражнения;
• проверка знаний – задания для самостоятельной работы.

Цели урока:

• дать понятие таблицы истинности;
• закрепление материала предыдущего урока “Алгебра высказываний”;
• использование информационных технологий;
• привитие навыка самостоятельного поиска нового материала;
• развитие любознательности, инициативы;
• воспитание информационной культуры.

План урока:

1. Организационный момент (2 мин).
2. Повторение материала предыдущего урока (устный опрос) (4 мин).
3. Объяснение нового материала (12 мин).
4. Закрепление

• разбор примера (5 мин);
• практические упражнения (10 мин);
• задания для самостоятельной работы (10 мин).

Оборудование и программный материал:

• белая доска;
• мультимедийный проектор;
• компьютеры;
• редактор презентаций MS PowerPoint 2003;
• раздаточный справочный материал “Таблицы истинности”;
• демонстрация презентации “Таблицы истинности”.

Ход урока

I. Организационный момент

Мы продолжаем изучение темы “Основы логики”. На предыдущих уроках мы увидели, что логика достаточно крепко связана с нашей повседневной жизнью, а также увидели, что почти любое высказывание можно записать в виде формулы.

II. Повторение материала предыдущего урока

Давайте вспомним основные определения и понятия:

III. Объяснение нового материала

Последние два примера относятся к сложным высказываниям. Как же определить истинность сложных высказываний?

Мы говорили, что она вычисляется. Для этого в логике существуют таблицы для вычисления истинности составных (сложных) высказываний. Они называются таблицами истинности.

Итак, тема урока ТАБЛИЦЫ ИСТИННОСТИ.

3.1) Определение. Таблица истинности – это таблица, показывающая истинность сложного высказывания при всех возможных значениях входящих переменных (Рисунок 1).

3.2) Разберем подробнее каждую логическую операцию в соответствии с ее определением:

1. Инверсия (отрицание) – это логическая операция, которая каждому простому высказыванию ставит в соответствие составное высказывание, заключающееся в том, что исходное высказывание отрицается.

Эта операция относится только к одной переменной, поэтому для нее отведено только две строки, т.к. одна переменная может иметь одно из двух значений: 0 или 1.

2. Конъюнкция (умножение)– это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания истинны.

Легко увидеть, что данная таблица действительно похожа на таблицу умножения.

3. Дизъюнкция (сложение) – это логическая операция, которая каждым двум простым высказываниям ставит в соответствие составное высказывание, являющееся ложным тогда и только тогда, когда оба исходных высказывания ложны.

Можно убедиться, что таблица похожа на таблицу сложения кроме последнего действия. В двоичной системе счисления 1 + 1 = 10, в десятичной – 1 + 1 = 2. В логике значения переменной 2 невозможно, рассмотрим 10 с точки зрения логики: 1 – истинно, 0 – ложно, т.о. 10 – истинно и ложно одновременно, чего быть не может, поэтому последнее действие строго опирается на определение.

4. Импликация (следование) – это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся ложным тогда и только тогда, когда условие истинное, а следствие ложно.

5. Эквиваленция (равносильность) – это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания одновременно истинны или ложны.

Последние две операции были разобраны нами на предыдущем уроке.

3.3) Разберем алгоритм составления таблицы истинности для сложного высказывания:

3.4) Рассмотрим пример составления таблицы истинности для сложного высказывания:

Пример. Построить таблицу истинности для формулы: А U В -> ¬А U С.

Решение (Рисунок 2)

Из примера видно, что таблицей истинности является не все решение, а только последнее действие (столбец, выделенный красным цветом).

IV. Закрепление.

Для закрепления материала вам предлагается решить самостоятельно примеры под буквами а, б, в, дополнительно г–ж (Рисунок 3).

V. Домашнее задание, обобщение материала.

Домашнее задание дано вам также на экране монитора (Рисунок 4)

Обобщение материала: сегодня на уроке мы научились определять истинность составных высказываний, но больше с математической точки зрения, так как вам были даны не сами высказывания, а формулы, отображающие их. На следующих уроках мы закрепим эти умения и постараемся их применить к решению логических задач.

Определение 1

Логическая функция – функция, переменные которой принимают одно из двух значений: $1$ или $0$.

Любую логическую функцию можно задать с помощью таблицы истинности: набор всех возможных аргументов записывается в левой части таблицы, а соответствующие значения логической функции – в правой части.

Определение 2

Таблица истинности – таблица, которая показывает, какие значения примет составное выражение при всех возможных наборах значений простых выражений, входящих в него.

Определение 3

Равносильными называются логические выражения, последние столбцы таблиц истинности которых совпадают. Равносильность обозначается с помощью знака $«=»$.

При составлении таблицы истинности важно учитывать следующий порядок выполнения логических операций:

Рисунок 1.

Приоритетом в выполнении порядка выполнения операций пользуются скобки.

Алгоритм построения таблицы истинности логической функции

Определяют количество строк: кол-во строк = $2^n + 1$ (для строки заголовка) , $n$ – количество простых выражений. Например, для функций двух переменных существует $2^2 = 4$ комбинации наборов значений переменных, для функций трех переменных – $2^3 = 8$ и т.д.

Определяют количество столбцов: кол-во столбцов = кол-во переменных + кол-во логических операций. При определении количества логических операций учитывают также порядок их выполнения.

Заполняют столбцы результатами выполнения логических операций в определенной последовательности, учитывая таблицы истинности основных логических операций.

Рисунок 2.

Пример 1

Составить таблицу истинности логического выражения $D=\bar{A} \vee (B \vee C)$.

Решение:

Определим количество строк:

кол-во строк = $2^3 + 1=9$.

Количество переменных – $3$.

1. инверсия ($\bar{A}$);
2. дизъюнкция, т.к. она находится в скобках ($B \vee C$);

3. дизъюнкция ($\overline{A}\vee \left(B\vee C\right)$) – искомое логическое выражение.

   Кол-во столбцов = $3 + 3=6$.

Заполним таблицу, учитывая таблицы истинности логических операций.

Рисунок 3.

Пример 2

По данному логическому выражению построить таблицу истинности:

Решение:

Определим количество строк:

Количество простых выражений – $n=3$, значит

кол-во строк = $2^3 + 1=9$.

Определим количество столбцов:

Количество переменных – $3$.

Количество логических операций и их последовательность:

1. отрицание ($\bar{C}$);
2. дизъюнкция, т.к. она находится в скобках ($A \vee B$);
3. конъюнкция ($(A\vee B)\bigwedge \overline{C}$);
4. отрицание, которое обозначим $F_1$ ($\overline{(A\vee B)\bigwedge \overline{C}}$);
5. дизъюнкция ($A \vee C$);
6. конъюнкция ($(A\vee C)\bigwedge B$);
7. отрицание, которое обозначим $F_2$ ($\overline{(A\vee C)\bigwedge B}$);

8. дизъюнкция – искомая логическая функция ($\overline{(A\vee B)\bigwedge \overline{C}}\vee \overline{(A\vee C)\bigwedge B}$).

Учимся составлять логические выражения из высказываний, определяем понятие “таблица истинности”, изучаем последовательность действий построения таблиц истинности, учимся находить значение логических выражений посредством построения таблиц истинности.

Цели урока:

1. Обучающие:
   1. Научить составлять логические выражения из высказываний
   2. Ввести понятие “таблица истинности”
   3. Изучить последовательность действий построения таблиц истинности
   4. Научить находить значение логических выражений посредством построения таблиц истинности
   5. Ввести понятие равносильности логических выражений
   6. Научить доказывать равносильность логических выражений, используя таблицы истинности
   7. Закрепить навыки нахождения значений логических выражений посредством построения таблиц истинности
2. Развивающие:
   1. Развивать логическое мышление
   2. Развивать внимание
   3. Развивать память
   4. Развивать речь учащихся
3. Воспитательные:
   1. Воспитывать умение слушать учителя и одноклассников
   2. Воспитывать аккуратность ведения тетради
   3. Воспитывать дисциплинированность

Ход урока

Организационный момент

Здравствуйте, ребята. Мы продолжаем изучать основы логики и тема нашего сегодняшнего урока «Составление логических выражений. Таблицы истинности». Изучив данную тему, вы научитесь, как из высказываний составляются логические формы, и определять их истинность посредством составления таблиц истинности.

Проверка домашнего задания

Записать решение домашних задач на доску
Все остальные откройте тетради, я пройду, проверю, как вы выполнили домашнее задание
Давайте еще раз повторим логические операции
В каком случае в результате операции логического умножения составное высказывание будет истинно?
Составное высказывание, образованное в результате операции логического умножения, истинно тогда и только тогда, когда истинны все входящие в него простые высказывания.
В каком случае в результате операции логического сложения составное высказывание будет ложно?
Составное высказывание, образованное в результате операции логического сложения, ложно тогда, когда ложны все входящие в него простые высказывания.
Как влияет инверсия на высказывание?
Инверсия делает истинное высказывание ложным и, наоборот, ложное – истинным.
Что вы можете сказать об импликации?
Логическое следование (импликация) образуется соединением двух высказываний в одно с помощью оборота речи «если…, то…».
Обозначается А -> В
Составное высказывание, образованное с помощью операции логического следования (импли­кации), ложно тогда и только тогда, когда из истинной предпосылки (первого высказывания) следует ложный вывод (второе высказывание).
Что вы можете сказать о логической операции эквивалентности?
Логическое равенство (эквивалентность) образуется соединением двух высказываний в одно с помощью оборота речи “... тогда и только тогда, когда…”, “…в том и только в том случае…”
Составное высказывание, образованное с помощью логической операции эквивалентности истинно тогда и только тогда, когда оба высказывания одновременно либо ложны, либо истинны.

Объяснение нового материала

Хорошо, повторили пройденный материал, переходим к новой теме.

На прошлом уроке мы находили значение составного высказы­вания путем подстановки исходных значений входящих логических переменных. А сегодня мы узнаем, что можно построить таблицу истинности, которая определяет истинность или лож­ность логического выражения при всех возможных комбинациях исходных значе­ний простых высказываний (логических переменных) и, что можно определить значения исходных логических переменных, зная какой нам нужен результат.

Еще раз рассмотрим наш пример с прошлого урока

и построим таблицу истинности для этого составного высказывания

При построении таблиц истинности есть определенная последовательность действий. Давайте запишем

1. Необходимо определить количество строк в таблице истинности.

• количество строк = 2 n , где n – количество логических переменных

Записали. Строим таблицу истинности
Что мы делаем во-первых?
Определить количество столбцов в таблице
Как мы это делаем?
Считаем количество переменных. В нашем случае логическая функция содержит 2 переменные
Какие?
А и В
Значит сколько строк будет в таблице?
Количество строк в таблице истинности должно быть равно 4.
А если 3 переменных?
Количество строк = 2³ = 8
Верно. Что делаем дальше?
Определяем количество столбцов = количеству логических переменных плюс количество логических операций.
Сколько будет в нашем случае?
В нашем случае количество переменных равно двум, а количество логических операции - пяти, то есть количество столбцов таблицы истинности равно семи.
Хорошо. Дальше?
Строим таблицу с указанным количеством строк и столбцов, обозначаем столбцы и вносим в таблицу возможные наборы значений исходных логических переменных и заполняем таблицу истинности по столбцам.
Какую операцию будем выполнять первой? Только учитывайте скобки и приоритеты
Можно сначала выполнить логическое отрицание или найти значение сначала в первой скобке, затем инверсию и значение во второй скобке, затем значение между этими скобками

Теперь мы можем определить значение логической функции для любого набора значении логических переменных
Теперь записываем пункт “Равносильные логические выражения”.
Логические выра­жения, у которых последние столбцы таблиц истинности сов­падают, называются равносильными. Для обозначения равносильных логических выражений используется знак “ = “,
Докажем, что логические выражения ┐ А& ┐В и AvB равносильны. Построим сначала таблицу истинности логического выражения

Сколько столбцов будет в таблице? 5
Какую операцию будем выполнять первой? Инверсию А, инверсию В

Теперь построим таблицу истинности логического выражения AvB
Сколько строк будет в таблице? 4
Сколько столбцов будет в таблице? 4

Мы все понимаем, что, если нужно найти отрицание для всего выражения, то приоритет, в нашем случае, принадлежит дизъюнкции. Поэтому сначала выполняем дизъюнкцию, а затем инверсию. К тому же мы можем переписать наше логическое выражение AvB. Т.к. нам нужно найти отрицание всего выражения, а не отдельных переменных, то инверсию можно вынести за скобки ┐(AvB), а мы знаем, что сначала находим значение в скобках

Построили таблицы. Теперь давайте, сравним значения в последних столбцах таблиц истинности, т.к. именно последние столбцы являются результирующими. Они совпадают, следовательно, логические выражения равносильны и мы можем поставить между ними знак “=”

Решение задач

1.

Сколько переменных содержит данная формула? 3
Сколько строк и столбцов будет в таблице? 8 и 8
Какова будет в нашем примере последовательность операций? (инверсия, операции в скобках, операцию за скобкой)

2. Докажите с помощью таблиц истинности равносильность следую­щих логических выражений:

(А → B) И (Av┐B)

Какой делаем вывод? Данные логические выражения не равносильны

Домашнее задание

Доказать, используя таблицы истинности, что логические выражения

┐A v ┐B и А&В равносильны

Объяснение нового материала (продолжение)

Мы уже несколько уроков подряд используем понятие “таблица истинности”, а что же такое таблица истинности , как вы думаете?
Таблица истинности – это таблица, устанавливающая соответствие между возможными наборами значений логических переменных и значениями функций.
Как вы справились с домашним заданием, какой у вас получился вывод?
Выражения равносильны
Помните, на предыдущем уроке мы из составного высказывания составляли формулу, заменяя простые высказывания 2*2=4 и 2*2=5 переменными А и В
Теперь давайте учиться составлять логические выражения из высказываний

Запишите задание

Записать в виде логической формулы высказывания:

1) Если Иванов здоров и богат, то он здоров

Анализируем высказывание. Выявляем простые высказывания

А – Иванов здоров
В – Иванов богат

Хорошо, тогда как будет выглядеть формула? Только не забудьте, чтобы не терялся смысл высказывания, расставить скобки в формуле

2) Число является простым, если оно делится только на 1 и само на себя

А - число делится только на 1
В - число делится только на себя
С - число является простым

3) Если число делится на 4, оно делится на 2

А - делится на 4
В - делится на 2

4) Произвольно взятое число либо делится на 2,либо делится на 3

А - делится на 2
В - делится на 3

5) Спортсмен подлежит дисквалификации, если он некорректно ведет себя по отношению к сопернику или судье, и если он принимал «допинг».

А - спортсмен подлежит дисквалификации
В - некорректно ведет себя по отношению к сопернику
С - некорректно ведет себя по отношению к судье
D - принимал «допинг».

Решение задач

1. Построить таблицу истинности для формулы

((p&q)→ (p→ r)) v p

Объясняем сколько строк и столбцов будет в таблице? (8 и 7) Какова будет последовательность операций и почему?

Посмотрели на последний столбец и сделали вывод, что при любом наборе входных параметров формула принимает истинное значение, такая формула называется тавтологией. Запишем определение:

Формула называется законом логики, или тавтологией, если она принимает тождественно значение “истина” при любом наборе значений переменных, входящих в эту формулу.
А если все значения будут ложны, как вы думаете, что можно сказать о такой формуле?
Можно сказать, что формула невыполнима

2. Записать в виде логической формулы высказывания:

Администрация морского порта издала следующее распоряжение:

1. Если капитан корабля получает специальное указание, то он должен покинуть порт на своем корабле
2. Если капитан не получает специального указания, то он не должен покидать порт, или он впредь лишается допуска в этот порт
3. Капитан или лишается допуска в этот порт, или не получает специального указания

Выявляем простые высказывания, составляем формулы

• А - капитан получает специальное указание
• В - покидает порт
• С - лишается допуска в порт

1. ┐А→(┐В v С)
2. С v ┐А

3. Записать составное высказывание “(2*2=4 и 3*3 = 9) или (2*2≠4 и 3*3≠9)” в форме логического выражения. Построить таблицу истинности.

А={2*2=4} B={3*3 = 9}

(А&В) v (┐А&┐В)

Домашнее задание

Выбрать составное высказывание, имеющее ту же таблицу истинно­сти, что и не (не А и не (В и С)).

1. АиВ или СиА;
2. (А или В) и (А или С);
3. А и (В или С);
4. А или (не В или не С).

Логическая функция - это функция, в которой переменные принимают только два значения: логическая единица или логический ноль. Истинность или ложность сложных суждений представляет собой функцию истинности или ложности простых. Эту функцию называют булевой функцией суждений f (a, b).

Любая логическая функция может быть задана с помощью таблицы истинности, в левой части которой записывается набор аргументов, а в правой части - соответствующие значения логической функции.

При построении таблицы истинности необходимо учитывать порядок выполнения логических операций. Операции в логическом выражении выполняются слева направо с учетом скобок в следующем порядке:

• 1. инверсия;
• 2. конъюнкция;
• 3. дизъюнкция;
• 4. импликация и эквивалентность.

Для изменения указанного порядка выполнения логических операций используются круглые скобки.

Предлагается следующий алгоритм построения таблицы истинности .

• 1. Определить количество наборов входных переменных - всевозможных сочетаний значений переменных, входящих в выражения, по формуле: Q=2 n , где n - количество входных переменных. Оно определяет количество строк таблицы.
• 2. Внести в таблицу все наборы входных переменных.
• 3. Определить количество логических операций и последовательность их выполнения.
• 4. Заполнить столбцы результатами выполнения логических операций в обозначенной последовательности.

Чтобы не повторить или не пропустить ни одного возможного сочетания значений входных переменных, следует пользоваться одним из предлагаемых ниже способов заполнения таблицы.

Способ 1. Каждый набор значений исходных переменных есть код числа в двоичной системе счисления, причем количество разрядов числа равно количеству входных переменных. Первый набор - число 0. Прибавляя к текущему числу каждый раз по 1, получаем очередной набор. Последний набор - максимальное значение двоичного числа для данной длины кода.

Например, для функции от трех переменных последовательность наборов состоит из чисел:

Способ 2. Для функции от трех переменных последовательность данных можно получить следующим путем:

• а) разделить колонку значений первой переменной пополам и заполнить верхнюю половину нулями, нижнюю половину единицами;
• б) в следующей колонке для второй переменной половинку снова разделить пополам и заполнить группами нулей и единиц; аналогично заполнить вторую половинку;
• в) так делать до тех пор, пока группы нулей и единиц не будут состоять из одного символа.

Способ 3. Воспользоваться известной таблицей истинности для двух аргументов. Добавляя третий аргумент, сначала записать первые 4 строки таблицы, сочетая их со значением третьего аргумента, равным 0, а затем еще раз записать эти же 4 строки, но теперь уже со значением третьего аргумента, равным 1. В результате в таблице для трех аргументов окажется 8 строк:

Например, построим таблицу истинности для логической функции:

Количество входных переменных в заданном выражении равно трем (A,B,C) . Значит, количество входных наборов Q=2 3 =8 .

Столбцы таблицы истинности соответствуют значениям исходных выражений A,B,C , промежуточных результатов и (B V C ), а также искомого окончательного значения сложного арифметического выражения:

• 0 0 0 1 0 0
• 0 0 1 1 1 1
• 0 1 0 1 1 1
• 0 1 1 1 1 1
• 1 0 0 0 0 0
• 1 0 1 0 1 0
• 1 1 0 0 1 0
• 1 1 1 0 1 0
• 7.4. Логические функции и их преобразования. Законы логики

Для операций конъюнкции, дизъюнкции и инверсии определены законы булевой алгебры, позволяющие производить тождественные (равносильные) преобразования логических выражений .

Законы логики

• 1. ¬¬ А
• 2. A&B
• 3. AVB
• 4. A&(B&C)
• 5. AV(BVC)
• 6. A&(BVC)
• 7. AV(B&C)
• 8. A&A
• 9. AVA
• 10. AV¬A
• 11. A&¬A
• 12. A&И
• 13. AVИ
• 14. A&Л
• 15. AVЛ
• 16. ¬(A&B)
• 17. ¬(AVB)
• 18. A => B

Основываясь на законах, можно выполнять упрощение сложных логических выражений. Такой процесс замены сложной логической функции более простой, но равносильной ей, называется минимизацией функции.

Пример 1. Упростить выражения так, чтобы в полученных формулах не содержалось отрицания сложных высказываний.

Решение

Пример 2. Минимизировать функцию

При упрощении выражения использовались формулы поглощения и склеивания.

Пример 3. Найти отрицание следующего высказывания: "Если урок будет интересным, то никто из учеников (Миша, Вика, Света) не будет смотреть в окно".

Решение

Обозначим высказывания:

Y - "Урок интересный";

M - "Миша смотрит в окно";

B - "Вика смотрит в окно";

C - "Света смотрит в окно".

При упрощении выражения использовались формула замены операций и закон де Моргана.

Пример 4. Определить участника преступления, исходя из двух посылок: логический компьютер таблица

• 1) "Если Иванов не участвовал или Петров участвовал, то Сидоров участвовал";
• 2) "Если Иванов не участвовал, то Сидоров не участвовал".

Решение

Составим выражения:

I - "Иванов участвовал в преступлении";

P - "Петров участвовал в преступлении";

S - "Сидоров участвовал в преступлении".

Запишем посылки в виде формул:

Проверим результат, используя таблицу истинности:

Ответ: Иванов участвовал в преступлении.

Построение логической функции по ее таблице истинности

Мы научились составлять таблицу истинности для логической функции. Попробуем решить обратную задачу.

Рассмотрим строки, где значение истинности функции Z истинно (Z=1). Функцию для этой таблицы истинности можно составить следующим образом: Z(X,Y) = (¬ X& ¬Y)V(X& ¬Y).

Каждой строке, где функция истинна (равна 1), соответствует скобка, представляющая собой конъюнкцию аргументов, причем если значение аргумента О, то мы берем его с отрицанием. Все скобки соединены между собой операцией дизъюнкции. Полученную формулу можно упростить, применив законы логики:

Z(X,Y) <=> ((¬X& ¬Y) VX)&((¬X&Y)V ¬Y) <=> (XV(¬X& ¬Y)) &(¬YV(¬X&¬Y)) <=> ((XV¬X)&(XV ¬Y))&((Y¬V ¬X)&(¬YV ¬Y)) <=> (1&(XV ¬Y))&((¬YV ¬X)& ¬Y)<=> (XV ¬Y)&((¬YV ¬X)& ¬Y).

Проверьте полученную формулу: составьте таблицу истинности для функции Z(X,Y).

Запишите правила конструирования логической функции по ее таблице истинности:

• 1. Выделить в таблице истинности те строки, в которых значение функции равно 1.
• 2. Выписать искомую формулу в виде дизъюнкции нескольких логических элементов. Число этих элементов равно числу выделенных строк.
• 3. Каждый логический элемент в этой дизъюнкции записать в виде конъюнкции аргументов функции.
• 4. Если значение какого-либо аргумента функции в соответствующей строке таблице равно 0, то этот аргумент мы берем с отрицанием.

В цифровой схемотехнике цифровой сигнал - это сигнал, который может принимать два значения, рассматриваемые как логическая "1" и логический "0".

Логические схемы могут содержать до 100 миллионов входов и такие гигантские схемы существуют. Представьте себе, что булева функция (уравнение) такой схемы была потеряна. Как восстановить её с наименьшими потерями времени и без ошибок? Наиболее продуктивный способ - разбить схему на ярусы. При таком способе записывается выходная функция каждого элемента в предыдущем ярусе и подставляется на соответствующий вход на следующем ярусе. Этот способ анализа логических схем со всеми нюансами мы сегодня и рассмотрим.

Логические схемы реализуются на логических элементах: "НЕ", "И", "ИЛИ", "И-НЕ", "ИЛИ-НЕ", "Исключающее ИЛИ" и "Эквивалентность". Первые три логических элемента позволяют реализовать любую, сколь угодно сложную логическую функцию в булевом базисе . Мы будем решать задачи на логические схемы, реализованные именно в булевом базисе.

Для обозначения логических элементов используется несколько стандартов. Наиболее распространёнными являются американский (ANSI), европейский (DIN), международный (IEC) и российский (ГОСТ). На рисунке ниже приведены обозначения логических элементов в этих стандартах (для увеличения можно нажать на рисунок левой кнопкой мыши).

На этом уроке будем решать задачи на логические схемы, на которых логические элементы обозначены в стандарте ГОСТ.

Задачи на логические схемы бывают двух видов: задача синтеза логических схемы и задачи анализа логических схем. Мы начнём с задачи второго типа, так как в таком порядке удаётся быстрее научиться читать логические схемы.

Чаще всего в связи с построением логических схем рассматриваются функции алгебры логики:

• трёх переменных (будут рассмотрены в задачах анализа и в одной задаче синтеза);
• четырёх переменных (в задачах синтеза, то есть в двух последних параграфах).

Рассмотрим построение (синтез) логических схем

• в булевом базисе "И", "ИЛИ", "НЕ" (в предпоследнем параграфе);
• в также распространённых базисах "И-НЕ" и "ИЛИ-НЕ" (в последнем параграфе).

Задача анализа логических схем

Задача анализа заключается в определении функции f , реализуемой заданной логической схемой. При решении такой задачи удобно придерживаться следующей последовательности действий.

1. Логическая схема разбивается на ярусы. Ярусам присваиваются последовательные номера.
2. Выводы каждого логического элемента обозначаются названием искомой функции, снабжённым цифровым индексом, где первая цифра - номер яруса, а остальные цифры - порядковый номер элемента в ярусе.
3. Для каждого элемента записывается аналитическое выражение, связывающее его выходную функцию с входными переменными. Выражение определяется логической функцией, реализуемой данным логическим элементом.
4. Производится подстановка одних выходных функций через другие, пока не получится булева функция, выраженная через входные переменные.

Пример 1.

Решение. Разбиваем логическую схему на ярусы, что уже показано на рисунке. Запишем все функции, начиная с 1-го яруса:

x , y , z :

Пример 2. Найдите булеву функцию логической схемы и составьте таблицу истинности для логической схемы.

Пример 3. Найдите булеву функцию логической схемы и составьте таблицу истинности для логической схемы.

Продолжаем искать булеву функцию логической схемы вместе

Пример 4. Найдите булеву функцию логической схемы и составьте таблицу истинности для логической схемы.

Решение. Разбиваем логическую схему на ярусы. Запишем все функции, начиная с 1-го яруса:

Теперь запишем все функции, подставляя входные переменные x , y , z :

В итоге получим функцию, которую реализует на выходе логическая схема:

.

Таблица истинности для данной логической схемы:

Пример 5. Найдите булеву функцию логической схемы и составьте таблицу истинности для логической схемы.

Решение. Разбиваем логическую схему на ярусы. Структура данной логической схемы, в отличие от предыдущих примеров, имеет 5 ярусов, а не 4. Но одна входная переменная - самая нижняя - пробегает все ярусы и напрямую входит в логический элемент в первом ярусе. Запишем все функции, начиная с 1-го яруса:

Теперь запишем все функции, подставляя входные переменные x , y , z :

В итоге получим функцию, которую реализует на выходе логическая схема:

.

Таблица истинности для данной логической схемы:

Задача синтеза логических схем в булевом базисе

Разработка логической схемы по её аналитическому описанию имеет название задачи синтеза логической схемы.

Каждой дизъюнкции (логической сумме) соответствует элемент "ИЛИ", число входов которого определяется количеством переменных в дизъюнкции. Каждой конъюнкции (логическому произведению) соответствует элемент "И", число входов которого определяется количеством переменных в конъюнкции. Каждому отрицанию (инверсии) соответствует элемент "НЕ".

Часто разработка логической схемы начинается с определения логической функции, которую должна реализовать логическая схемы. В этом случае дана только таблица истинности логической схемы. Мы разберём именно такой пример, то есть, решим задачу, полностью обратную рассмотренной выше задаче анализа логических схем.

Пример 6. Построить логическую схему, реализующую функцию с данной таблицей истинности.