2.1. Логика высказываний

2.1.1. Булева алгебра.

Простейшей логической моделью представления знаний является логика высказываний (ЛВ).

Высказывание – это утверждение, значение которого может быть истинным или ложным. Данное значение называется истинностью высказывания.

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

1 – истина (true);

0 – ложь (false).

Атом – элементарное высказывание, обозначается строчной латинской буквой, например: p, q, f и т.д.

При построении более сложных высказываний (формул) используются логические операции (связки).

Дизъюнкцией (логическим «или», логическим сложением) называется логическая операция, которая любым двум высказываниям x, y сопоставляет единственное высказывание, истинностное значение которого определяется следующей таблицей истинности (рис ?):

x	y	xy
0	0	0
0	1	1
1	0	1
1	1	1

Рис. ? Таблица истинности для операции дизъюнкции

Конъюнкцией (логическим «и», логическим умножением) называется логическая операция, которая любым двум высказываниям x, y сопоставляет единственное высказывание, истинностное значение которого определяется следующей таблицей истинности:

x	y	xy
0	0	0
0	1	0
1	0	0
1	1	1

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

x	x
0	1
1	0

Импликацией называется логическая операция, которая любым двум высказываниям x, y сопоставляет единственное высказывание, истинностное значение которого определяется следующей таблицей истинности:

x	y	xy
0	0	1
0	1	1
1	0	0
1	1	1

Эквивалентностью (эквиваленцией) называется логическая операция, которая любым двум высказываниям x, y сопоставляет единственное высказывание, истинностное значение которого определяется следующей таблицей истинности:

x	y	xy
0	0	1
0	1	0
1	0	0
1	1	1

Литералом или литерой называется атом или его отрицание.

Например: p, q, l

Рекуррентное определение формул:

1. Атом – это формула

2. Если F – формула, то F – формула

3. Если F_1, F₂ - формулы, то F₁F₂, F₁F₂, F₁F₂, F₁F₂ – формулы.

Интерпретация формулы – это отображение, ставящее в соответствии истинностным значениям атомов истинностное значение формулы.

Например:

Пусть имеется формула:

(pq)l;

пусть p=0, q=0, l=0, следовательно, F=1

p=1, q=0, l=0, следовательно, F=0

Формула, истинная при всех интерпретациях, называется общезначимой. Формула, ложная при всех интерпретациях, называется противоречивой. Формулы f и q являются эквивалентными, если они истинны в одних и тех же интерпретациях.

Множество {0,1} (true, false) c определенными на нем операциями конъюнкции и дизъюнкции образует булеву алгебру:

({0,1}, , ) – Булева алгебра

Для любых формул F₁, F₂, F₃ справедливы следующие свойства.

1. Коммутативность

F₁F₂F₂F₁.

F₁F₂F₂F_1..

2. Ассоциативность

(F₁F₂)F₃F₁(F₂F₃).

(F₁F₂)F₃F₁(F₂F₃).

3. Дистрибутивность

F₁(F₂F₃)(F₁F₂)(F₁F₃);

F₁(F₂F₃)(F₁F₂)(F₁F₃).

4. Законы единицы

F1F; F11;

5. Законы нуля

F0F; F00;

6. Закон исключённого третьего

FF1.

«закон» противоречия

FF0.

7. Законы поглощения

F₁(F₁F₂)F₁;

F₁(F₁F₂)F₁.

8. Законы де Моргана

(F₁F₂)F₁F_2;

(F₁F₂)F₁F₂.

9. Правила замены

F₁F₂F₁F₂;

F₁F₂=(F₁F₂)(F₂F₁)(F₁F₂)(F₂F₁).

10.  FF.

Все приведенные выше законы легко доказываются с помощью таблиц истинности.