Решение задач с помощью алгебры высказываний
Исследование рассуждений
Отношение логического следования используется при исследовании рассуждений.
Задача 1. Если 6 – составное число (S), то 12 – составное число (W). Если 12 – составное число, то существует простое число, больше чем 12 (P). Если существует простое число больше 12, то существует составное число больше 12 (C). Если 6 делится на 2 (D), то 6 – составное число. Число 12 составное. Следовательно, 6 – составное число.
Посылки: 
, 
, 
, 
, W
Заключение: S
Решение:
Данное высказывание тавтологией не является, значит из указанных посылок не следует высказывание «6 – составное число».
Задача 2. Я пойду в кино на новую комедию (A) или на занятия по математической логике (B). Если я пойду в кино, то я от всей души посмеюсь (C). Если я пойду на занятия по математической логике, то испытаю удовольствие от логических рассуждений (D). Следовательно, или я от всей души посмеюсь или испытаю удовольствие от логических рассуждений.
Посылки: 
, 
, 
Заключение: 
Решение:
Значит из данных посылок следует .
Задача 3. Я пойду домой (H) или останусь здесь и выпью стаканчик (S). Я не пойду домой. Следовательно, я останусь и выпью.
Посылки: 
, 
Заключение: S
Решение:
Значит, высказывание «я останусь и выпью» является логическим следствием из данных посылок.
Задача 4. Если Джон ляжет сегодня поздно (S), он будет утром в отупении (D). Если он ляжет не поздно, то ему будет казаться, что не стоит жить (L). Следовательно, или Джон будет завтра в отупении, или ему будет казаться, что не стоит жить.
|
|
|
Посылки: 
, 
Заключение: 
Решение:
Значит из данных посылок следует 
.
Задача 5. Или Сэлли и Боб одного возраста (S), или Сэлли старше Боба (O). Если Сэлли и Боб одного возраста, то Нэнси и Боб не одного возраста (N). Если Сэлли старше Боба, то Боб старше Уолтера (W). Следовательно, или Нэнси и Боб не одного возраста, или Боб старше Уолтера.
Решение:
Посылки: 
, 
, 
Заключение: 
Значит из данных посылок следует .
Получение логических следствий из данных формул и посылок для данных логических следствий
Логические следствия находят следующим образом:
1) все посылки соединяются конъюнкцией и находятся СКНФ полученной формулы.
2) при выборе любых элементарных дизъюнкций и конъюнкций любых нескольких элементарных дизъюнкций, взятых по два, три и т.д.
получаются все возможные заключения из данных посылок.
Задача 1. Даны посылки: A и A 
B
Решение:
Логические следствия:
1. 
;
2. 
;
3. 
;
4. 
;
5. 
;
6. 
;
7. 
.
Задача 2. Даны посылки: 
Решение:
Логические следствия:
|
|
|
1. 
;
2. 
;
3. 
;
4. 
;
5. 
;
6. 
;
7. 
.
Задача 3. Даны посылки: 
Решение:
Логические следствия:
1. 
; 
2. 
;
3. 
;
4. 
;
5. 
;
6. 
;
7. 
;
Задача 4. Найти формулу F(X, Y), зависящую только от переменных X и Y и являющуюся логическим следствием указанных формул (посылок):
Решение:
Составим таблицу истинности для формул, являющихся посылками:
| X | Y | Z | V | 
| 
| 
| 
| |
| 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 | 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 | 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 | 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 | 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1 1 | 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 | 1 0 1 0 1 1 1 1 1 0 1 0 1 1 1 1 | 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 | * |
В правом столбце звездочками отметим те строки, в которых все четыре посылки принимают значение 1. Этому требованию удовлетворяет лишь 15-я строка, в которой λ (X) = 0 и λ (Y) = 0. Следовательно, надо найти такую формулу F (X, Y), для которой F (0, 0) = 1, то такая формула будет логическим следствием четырех данных посылок. Ищем такую формулу, используя СДНФ и считаем, что на всех других наборах значений переменных искомая формула обращается в 0:
F (0, 1) = F (1, 0) = F (1, 1) = 0.
|
|
|
Получаем F (X, Y) 
.
Задача 5. Найти формулу F(X, Y), зависящую только от переменных X и Y и являющуюся логическим следствием указанных формул (посылок):
Решение:
Составим таблицу истинности для формул, являющихся посылками:
| X | Y | Z | 
| 
| |
| 1 1 1 0 1 0 0 0 | 1 1 0 1 0 1 0 0 | 1 0 1 1 0 0 1 0 | 1 1 1 1 1 0 1 0 | 1 1 0 1 1 1 0 1 | * * * * |
Найдем такую формулу F (X, Y), для которой F (1, 1) = F (0, 1) = F (1, 0) = 1, которая будет логическим следствием двух данных посылок.
F (0, 0) = 0.
Получаем F (X, Y) 
.
Задача 6. Найти формулу F(X, Y), зависящую только от переменных X и Y и являющуюся логическим следствием указанных формул (посылок):
Решение:
Составим таблицу истинности для формул, являющихся посылками:
| X | Y | Z | 
| 
| 
| |
| 1 1 1 0 1 0 0 0 | 1 1 0 1 0 1 0 0 | 1 0 1 1 0 0 1 0 | 1 0 1 1 0 1 1 1 | 0 1 0 0 1 1 1 1 | 1 1 1 0 1 0 1 1 | * * |
Найдем такую формулу F (X, Y), для которой F (0, 0) = 1, которая будет логическим следствием трех данных посылок.
F (1, 0) = F (0, 1) = F (1, 1) = 0.
Получаем F (X, Y) 
.
Чтобы определить логическим следствием каких посылок является формула А (X1,X2,…,Xn), необходимо:
1) привести ее к СКНФ.
2) составить конъюнкции формулы А с недостающими в ее СКНФ элементарными дизъюнкциями, взятыми по одной, две, три и т.д. (всевозможные варианты). Полученные формулы и будут посылками, из которых следует данная формула А.
|
|
|
Найти все не тождественно ложные формулы алгебры высказываний, для которых следующая формула является логическим следствием:
Задача 1. 
Решение:
Недостающие дизъюнкции: 
Посылка:
Данная формула может логически следовать либо из самой себя, либо из тождественно ложной формулы.
Задача 2. 
Решение:
Недостающие дизъюнкции: 
Посылка:
Данная формула может логически следовать либо из самой себя, либо из тождественно ложной формулы.
Задача 3.
Решение:
Недостающие дизъюнкции: 
Посылки:
;
;
;
;
;
;
.
Данная формула может логически следовать либо из самой себя, либо из тождественно ложной формулы.
Задача 4. Найти недостающую посылку (формулу) F, зависящую лишь от указанных высказываний, чтобы была верна следующая выводимость:
╞ 
Решение:
Составим таблицу истинности для формул, являющихся посылками и заключением:
| X | Y | Z | V | 
| 
| 
| |
| 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 | 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 | 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 | 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 | 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 | 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 | 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 | * |
В правом столбце звездочками отметим те строки, в которых обе данные посылки принимают значение 1, а следствие принимает значение 0. Этому требованию удовлетворяет лишь 12-я строка, в которой λ (Z) = 1 и λ (V) = 1. Ясно, что при этих значениях Z и V искомая посылка F (Z, V) должна принимать значение 0, так как в противном случае формула 
не будет логическим следствием формул 
. Будем считать, что на других наборах значений высказываний Z и V формула F (Z, V) принимает значение 1. Итак, для искомой посылки F (Z, V) получаем следующую таблицу истинности:
| Z | V | F(Z, V) |
| 1 | 1 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 1 |
Находим СКНФ для искомой формулы. Получаем F (Z, V) 
.
Задача 5. Найти недостающую посылку (формулу) F, зависящую лишь от указанных высказываний, чтобы была верна следующая выводимость:
╞ 
Решение:
Составим таблицу истинности для формул, являющихся посылками и заключением:
| X | Y | Z | 
| 
| 
| |
| 1 1 1 0 1 0 0 0 | 1 1 0 1 0 1 0 0 | 1 0 1 1 0 0 1 0 | 1 1 1 0 1 1 0 1 | 1 0 1 0 1 0 1 1 | 0 1 1 0 1 1 1 1 | * |
В правом столбце звездочками отметим те строки, в которых обе данные посылки принимают значение 1, а следствие принимает значение 0. Этому требованию удовлетворяет лишь 1-я строка, в которой λ (X) = 1 и λ (Y) = 1. Будем считать, что на других наборах значений высказываний X и Y формула F (X, Y) принимает значение 1. Итак, для искомой посылки F (X, Y) получаем следующую таблицу истинности:
| X | Y | F(X, Y) |
| 1 | 1 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 1 |
Находим СКНФ для искомой формулы. Получаем F (X, Y) 
.
Задача 5. Найти недостающую посылку (формулу) F, зависящую лишь от указанных высказываний, чтобы была верна следующая выводимость:
╞ 
Решение:
Составим таблицу истинности для формул, являющихся посылками и заключением:
| X | Y | Z |
| 
| 
| |
| 1 1 1 0 1 0 0 0 | 1 1 0 1 0 1 0 0 | 1 0 1 1 0 0 1 0 | 1 1 1 0 1 1 0 1 | 1 0 1 0 1 0 1 1 | 0 1 1 0 1 1 1 1 | * |
В правом столбце звездочками отметим те строки, в которых обе данные посылки принимают значение 1, а следствие принимает значение 0. Этому требованию удовлетворяет лишь 1-я строка, в которой λ (X) = 1 и λ (Y) = 1. Будем считать, что на других наборах значений высказываний X и Y формула F (X, Y) принимает значение 1. Итак, для искомой посылки F (X, Y) получаем следующую таблицу истинности:
| X | Y | F (X, Y) |
| 1 | 1 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 1 |
Находим СКНФ для искомой формулы. Получаем F (X, Y) 
.
Задача 5. Найти недостающую посылку (формулу) F, зависящую лишь от указанных высказываний, чтобы была верна следующая выводимость:
╞ 
Решение:
Составим таблицу истинности для формул, являющихся посылками и заключением:
| X | Y | Z | 
| Z | |
| 1 1 1 0 1 0 0 0 | 1 1 0 1 0 1 0 0 | 1 0 1 1 0 0 1 0 | 0 0 0 1 0 1 0 0 | 1 0 1 1 0 0 1 0 | * |
В правом столбце отметим строку, в которой данная посылка принимает значение 1, а следствие принимает значение 0. Этому требованию удовлетворяет лишь 6-я строка, в которой λ (X) = 0, λ (Y) = 1 и λ (Z) = 0. Будем считать, что на других наборах значений высказываний X, Y, Z формула F (X, Y, Z) принимает значение 1. Итак, для искомой посылки F(X, Y, Z) получаем следующую таблицу истинности:
| X | Y | Z | F (X,Y, Z) |
| 1 1 1 0 1 0 0 0 | 1 1 0 1 0 1 0 0 | 1 0 1 1 0 0 1 0 | 1 1 1 1 1 0 1 1 |
Находим СКНФ для искомой формулы. Получаем
F (X, Y, Z) 
.
Дата добавления: 2018-09-22; просмотров: 286; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!