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

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

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

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

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

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

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

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

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

Введем необходимые понятия.


Определение. Формула G называется логическим следствием формул F1,F2,…,Fk, если для любой интерпретации j из того, что j(F1)=j(F2)=…=j(Fk)=1 следует, что j(G)=1.

В качестве примера рассмотрим следующую задачу: выяснить логично ли рассуждение молодого человека из §2. Напомним, что это рассуждение мы перевели на ….

Приведем противоположный пример. Докажем, что формула G=Y®X не является логическим следствием формул F1=XÚY, F2=X®Y, F3=Y. Для этого построим совместную таблицу истинности формул F1,F2,F3 и G.

Таблица 1.4

X Y F1=XÚY F2=X®Y F3=X G=Y®X
1 1 1 1 1 1
1 0 1 0 0 1
0 1 1 1 1 0
0 0 0 1 0 1

Мы видим (см. таблицу 1.4), сто если взять интерпретацию j, для которой j(х)=0, j(y)=1, (т.е. взять третью строку таблицы), то j(F1)=j(F2)=j(F3)=1, но j(G)=0. Следовательно, формула G не является логическим следствием формул F1,F2,F3.

Понятие логического следствия тесно связано с понятием выполнимости.


Определение. Множество формул {F1,F2,…,Fl} называется выполнимым, если существует интерпретация j такая, что j(F1)=j(F2)=…=j(Fl)=1.

Проверку выполнимости множества формул {F1,F2,…,Fl} можно провести построением совместной таблицы истинности этих формул. Если найдется хотя одна строка, в которой в столбцах формул F1,F2,…,Fl стоят единицы, то это множество формул выполнимо. Если такой строки нет, то множество формул невыполнимо. Так, множество формул {F1,F2,F3,G} из предыдущего примера выполнимо, поскольку в таблице 1.4 в первой строке в столбцах этих формул стоят единицы.

В теме 4 нам понадобится следующее утверждение.


Теорема 1.2 Формула G является логическим следствием формул F1,F2,…,Fk тогда и только тогда, когда множество формул


L={F1,F2,…,Fk,ØG}


невыполнимо.


Доказательство. Пусть формула G является следствием множества формул F1,…,Fk . Предположим, от противного, что множество L выполнимо. Это означает, что существует интерпретация y такая, что y(F1)=…=y(Fk)=y(ØG)=1. Но если y(F1)=…=y(Fk)=1, то y(G)=1, поскольку G – логическое следствие формул F1,…,Fk. Полученное противоречие y(ØG)=1 и y(G)=1 доказывает, что множество формул {F1,…,Fk,ØG} невыполнимо.

Пусть теперь множество формул L невыполнимо. Рассмотрим интерпретацию j такую, что j(F1)=…=j(Fk)=1. Поскольку L невыполнимо, то j(ØG)=0. Если j(ØG)=0, то j(G)=1. Следовательно, из равенств j(F1)=…=j(Fk)=1 следует равенство j(G)=1. Это означает, что G – логическое следствие множества формул F1,…,Fk.

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

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

Задачи

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

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

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

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

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

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

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


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

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