Автор: Пользователь скрыл имя, 10 Августа 2012 в 13:52, контрольная работа
Элементы математической логики. Основные понятия логики высказываний. Высказывание, основные логические операции. Логические переменные и формулы. Таблицы истинности логических операций и формул. Соглашение о приоритетах логических операций. и т.д.
.
A →(BC)(A → B) (A → C)
Решение.
Логические операции и их таблицы истинности
1. Конъюнкция – (), читается «x и y»
2. Дизъюнкция – ( ), читается «x или y».
3. Отрицание (инверсия) – (), читается «не x».
4. Импликация - (), читается «если х, то у».
5. Эквиваленция – (), читается «х если и только если у».
6. Штрих Шеффера – (), определяется как отрицание конъюнкции, т.е. читается «не x и y».
7. Стрелка Пирса – (), определяется как отрицание дизъюнкции, т.е. читается «не x или y».
8. Кольцевая сумма – (), определяется как отрицание эквиваленции (исключающее «или»), т.е. читается «или х, или у».
Вычисление значений логических выражений выполняется в определенном порядке, согласно их приоритету:
- Отрицание (инверсия)
- конъюнкция
- дизъюнкция
- импликация и эквивалентность
Операции одного приоритета выполняются слева направо. Для изменения порядка действий используются скобки.
Порядок действий в нашем примере:
1) BC
2) A → B
3) A → C
4) (A → B) (A → C)
5) A →(BC)
6) A →(BC)(A → B) (A → C)
Таблица истинности
0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 | 1 |
1 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 |
1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 |
Составим таблицу истинности для нашей формулы:
A | B | C | BC | A →B | A→C | (A→B) (A→C) | A →(BC) | Ф |
0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 1 |
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Т.е. правая часть выражения эквивалентна левой.
2.14 Установить эквивалентность формул:
а) с помощью таблиц истинности;
б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.
x(yz) и (xy)(xz)
a) Составим таблицу истинности для нашей формулы:
x | y | z | yz | Ф1= x(yz) | xy | xz | (xy)(xz) | Ф2 |
0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |
0 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 |
0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 |
1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 |
1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
Столбцы значений формул Ф1 и Ф2 совпадают, следовательно эти формулы эквивалентны.
б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.
Преобразуем выражение Ф1= x(yz)
По эквивалентному соотношению (16):
yz==d
По эквивалентному соотношению (15):
(использован закон Де-Моргана)
x(yz)= (с учетом двойного отрицания)
Используя дистрибутивность , получим:
x(yz)= - КНФ
Ф1= - СКНФ
Преобразуем теперь выражение Ф2=(xy)(xz):
t=(xy)= ; v=(xz)=;
(xy)(xz)=tv=
Ф2=(с учетом двойного отрицания)
; ; t==; v==;
Ф2=
По закону дистрибутивности:
=
Аналогично:
=
Ф2= (использовали свойство коммутативности)
Ф2 - СКНФ
Форма СКНФ(Ф1)= СКНФ(Ф2)
3.14 Упростить формулы: Ф=(A1A2) (A2A3) (A3A1)
Таблица истинности
0 | 0 | 0 | 1 |
0 | 1 | 0 | 1 |
1 | 0 | 0 | 0 |
1 | 1 | 1 | 1 |
Таблица для заданной формулы.
A1 | A2 | A3 | A1A2 | A2A3 | (A1A2) (A2A3) | A3A1 | Ф | |
0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 |
0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 |
0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 |
1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 |
1 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 |
1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 |
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |