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

Раздел 1. Математическая логика

Тема 1. Логика высказываний

Логика предикатов в качестве составной и наиболее простой части содержит логику высказываний.

§1. Высказывания и операции над ними

§2. Формулы логики высказываний, интерпретация

§3. Равносильность и законы логики высказываний

§4. Логическое следствие.

§5. Нормальные формы в логике высказываний

§6. Контактные схемы.

Задачи

Ответы, указания и решения

2. Приведем решение задачи 2.1. Рассмотрим высказывания: Х=«профсоюзы будут поддерживать губернатора», Y=«губернатор подпишет закон», U=«фермеры окажут губернатору поддержку», V=«губернатор наложит вето». Тогда рассуждение 2.1 представимо формулами F1=Y®X, F2=V®U, F3=(ØY&V)Ú(Y&ØV), G=ØXÚØY.


3. Тождественно истинны формулы а,в,ж и з. Остальные формулы тождественно истинными не являются.


4. В случаях а и б ответ положительный, в качестве F можно соответственно взять X&Y и Y. В случае в ответ отрицательный. Действительно, если интерпретация j такова, что j(Y)=1, j(Z)=0, то j(G)=0 независимо от j(F).


5. В случаях б и г формулы равносильны, в остальных нет.


6. Приведем решение задачи в случае г. Обозначим формулу Ø[(X&Y)ÚØZ] буквой F, а формулу Ø(Z®X)ÚØ(Z®Y) буквой G. Для доказательства равносильности надо из одной формулы с помощью законов логики высказываний получить другую. Применим к формуле F последовательно законы 18 и 17, получим формулу

F1=(ØXÚØY)&Z

Далее, используя дистрибутивность (закон 11), получим формулу

F2=(ØX&Z)Ú(ØY&Z).

Осталось отметить, что формула ØX&Z равносильна Ø(Z®X) (законы 19,18 и 20), а формула ØY&Z равносильна Ø(Z®Y). Следовательно, F равносильна G.


7. Приведем решение задачи 7а. Отметим вначале, что логичность следствия можно доказать, построив совместную таблицу истинности формул F1,F2,F3 и G, и убедиться в том, как только все формулы F1,F2,F3 принимают значение 1, то формула G принимает то же значение 1. Однако таблица будет довольно громоздкой, у нее будет 16 строк. Применим другой способ решения задачти. Предположим противное, пусть существует интерпретация j такая, что j(F1)=j(F2)=j(F3)=1, и j(G)=0. Тогда j(X)=1 и j(Y)=0, поскольку j(G)=0, и j(W)=0, поскольку j(F3)=1. Далее из равенств j(F2)=j(Z®W)=1 и j(W)=0 следует, что j(Z)=0. Но тогда j(F1)=j(X®YÚZ)=0, что противоречит условию j(F1)=1. Противоречие указывает, что G есть логическое следствие F1,F2, и F3.


8. Для решения задачи необходимо найти интерпретацию, при которой формулы F1,…,Fn, истинны, а G ложны. Такими интерпретациями являются

а) j(X)=j(Z)=1, j(Y)=j(W)=0;

б) j(X)=j(Y)=j(Z)=j(Z2)=1, j(Z1)=0;

в) j(X)=j(X1)=j(Y)=j(Y1)=0, j(Z)=1.


9. Рассуждения из задач 2.2 и 2.3 логично, а из задачи 2.4 – нелогично.


10. Приведем решение задачи 10.1. Рассмотрим высказывания: X=«Джонс не встречал Смита», Y=«Смит был убийцей», Z=«Джонс лжет», U=«убийство произошло после полуночи». Тогда рассуждения можно представить последовательностью формул: F1=X®YÚZ, F2=ØX&U, F3=U®YÚZ, F4=ØU, G=X. Существует интерпретация j такая, что j(F1)=j(F2)=j(F3)=j(F4)=1, j(G)=0, пример, j(X)=j(U)=0, j(Y)=j(Z)=1. Это означает, что G не является логическим следствием формул F1,…,F4 и что рассуждение нелогично.

Рассуждения из задач 10.2 – 10.4 также нелогичны.


11. Указание. Применить алгоритм приведения к ДНФ.


12. Указание. Применить алгоритм приведения к СДНФ.


13. Указание. Применить алгоритм приведения к КНФ.


14. Эквивалентные простые схемы приведены на следующих рисунках:

а)


б)


в)


15. Приведем решение задачи. Рассмотрим формулу F(X1,X2,X3), имеющую следующую таблицу истинности


X1 X2 X3 F
1 1 1 1
1 1 0 0
1 0 0 1
1 0 1 0
0 0 1 1
0 1 1 0
0 1 0 1
0 0 0 0

Атомарные формулы X1,X2 и Х3 обозначают выключатели. Заметим, что в таблице истинности значения атомарных формул X1,X2 и Х3 в каждой следующей строке отличаются от предыдущей только одной из атомарных формул, а значение формулы F меняется на противоположное. Это отражает требование о том, чтобы при нажатии на любой из выключателей свет выключался, если он был включен, и включался, если он был выключен.

По таблице истинности выпишем формулу F:

F=(X&Y&Z)Ú(X&ØY&ØZ)Ú(ØX&ØY&Z)Ú(ØZ&Y&ØZ).

Найдем наиболее простую формулу G равносильную F, в запись которой входят лишь связки &,Ú и Ø:

G=[X&((Y&Z)Ú(ØY&ØZ))]Ú[ØX&((ØY&Z)Ú(Y&ØZ))].

По формуле G построим искомую схему


16. Указание. Рассмотреть формулу F(X1,X2,X3), таблица истинности которой получается в соответствие с формулой

j(F)=max {j(X1),j(X2),j(X3)}.

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

Тема 2. Булевы функции

Тема 3. Логика предикатов

Тема 4. Метод резолюций

Раздел 2. Теория графов

Тема 5. Раскраски

Тема 6. Ориентированные графы и сети


Fair.ru Ярмарка сайтов
Rambler's Top100 Submitter.ru - Free promoting

Дизайн: Alex © 2002
Все вопросы и предложения можно направлять по адресу cad@mail.ustu.ru