Дискретная математика

.

1.14 Составить таблицы истинности для  формул:

A  →(BC)(A  → B) (A  → C)

Решение.        

Логические операции и их таблицы истинности

1. Конъюнкция – (), читается «x и y»

2. Дизъюнкция – ( ), читается «x или y».

3. Отрицание (инверсия) – (), читается «не x».

4. Импликация  -  (), читается «если х, то у».

5. Эквиваленция – (), читается «х если и только если у».

6. Штрих Шеффера – (), определяется как отрицание конъюнкции, т.е. читается «не x и y».

7. Стрелка Пирса – (), определяется как отрицание дизъюнкции, т.е. читается «не x или y».

8. Кольцевая сумма – (), определяется как отрицание эквиваленции (исключающее «или»), т.е. читается «или х, или у».

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

- Отрицание (инверсия)

- конъюнкция

- дизъюнкция

- импликация и эквивалентность

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

Порядок действий в нашем примере:

1)     BC

2)     A  → B

3)     A  → C

4)     (A → B) (A  → C)

5)     A →(BC)

6)     A  →(BC)(A  → B) (A  → C)

Таблица истинности

Составим таблицу истинности для нашей формулы:

Т.е. правая часть выражения эквивалентна левой.

2.14  Установить эквивалентность формул:

а) с помощью таблиц истинности;

б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.

x(yz) и (xy)(xz)

a) Составим таблицу истинности для нашей формулы:

Столбцы значений формул Ф1 и Ф2 совпадают, следовательно эти формулы эквивалентны.

б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.

Преобразуем выражение Ф1= x(yz)

По эквивалентному соотношению (16):

yz==d

По эквивалентному соотношению (15):

(использован закон Де-Моргана)

x(yz)= (с учетом двойного отрицания)

Используя дистрибутивность , получим:

x(yz)= - КНФ

Ф1= - СКНФ

Преобразуем теперь выражение Ф2=(xy)(xz):

t=(xy)= ; v=(xz)=;

(xy)(xz)=tv=

Ф2=(с учетом двойного отрицания)

; ; t==; v==;

Ф2=

По закону дистрибутивности:

=

Аналогично:

=

Ф2= (использовали свойство коммутативности)

Ф2  - СКНФ

Форма СКНФ(Ф1)= СКНФ(Ф2)

3.14 Упростить формулы: Ф=(A1A2) (A2A3) (A3A1)

Таблица истинности

Таблица для заданной формулы.

A1=A,  A2=B, A3=C

Так как в таблице только одно значение равно 0, то Ф=

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

Де-Моргана

и  двойного отрицания

Ф=

Последний столбец полностью совпадает с предыдущем, что свидетельствует об эквивалентности формул.

4.14 Записать формулы в виде, содержащем только операции  , ,  над простыми переменными

Ф=A

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

- Отрицание (инверсия)

- дизъюнкция

- импликация

Составим совершенную дизъюнктивную нормальную форму (СДНФ) формулы по таблице истинности.

Для этого выпишем наборы значений переменных, на которых формула принимает значение 1 (=1): {(000),(001)}.

Теперь применяем правило, по которому СДНФ функции содержит столько конъюнкт, сколько единиц в столбце значений ; каждому единичному  набору нулей и единиц  соответствует конъюнкта всех переменных, в которых взято с отрицанием, если , и без отрицания, если. Итак, СДНФ нашей формулы содержит дизъюнкцию двух конъюнкт вида (знак  опустим): 

A =

Проверим по таблице. Вычисления по правой и левой частям совпадает!

13.14 Упростить схемы

 Решение:

         Cоставим функцию проводимости для данной схемы

F(x,y,z)=(y)((xy))

Используя один из методов,  например, метод элементарных преобразований, упрощаем эту функцию:

Для определения МДНФ булевой функции, сначала надо найти её СДНФ, затем каждую элементарную конъюнкцию СДНФ отметить единицей в соответствующей ячейке карты Карно.

Составим совершенную дизъюнктивную нормальную форму (СДНФ) формулы по таблице истинности.

Для этого выпишем наборы значений переменных, на которых формула принимает значение 1 (F=1): {(000),(010),(1,1,0),(1,1,1)}.

F=

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

Последний столбец таблицы истинности подтверждает эквивалентность формул.

Упрощенная схема.

Список литературы

1. Л.Н. Астраханцева, Л.Н.Ким,  М.Ж.Байсалова Дискретная математика. Методические указания и задания к выполнению расчетно-графических работ (для студентов очной формы обучения специальности 050704 – Вычислительная техника и программное обеспечение), Часть 1, АИЭИС

2. Л.Н. Астраханцева. Дискретная математика. Конспект лекций для студентов всех форм обучения специальностей 050704 – Вычислительная техник и программное обеспечение. Электронное пособие. АИЭИС.

3. .     Судоплатов С.В., Овчинникова Е.В. Элементы дискретной  математики. – М.: ИНФРА-М, Новосибирск: изд-во НГТУ, 2002.- 280 с.   

7