1. Всякое предложение, о к-ом можно определенно сказать истинно оно или ложно наз-ся высказыванием.

Отрицанием высказывания А наз-ся выск-ие , к-ое истинно тогда и только тогда, когда А ложно.

-ф-ия истинности, -значение истинности выск-ия А.

Конъюнкцией(логическим умножением) двух выск-ий А, В наз-ся выск-ие , к-ое истинно тогда и только тогда,когда истинны одновременно оба выск-ия.

Дизъюнкцией(логическим сложением) двух высказываний А, В наз-ся выск-ие , к-ое ложно тогда и только тогда, когда ложны одновременно оба выск-ия.

Импликацией двух выск-ий А, В наз-ся выск-ие , к-ое ложно тогда и только тогда, когда выск-ие А истинно, а В ложно. Эквивалентностью двух выск-ий А, В наз-ся выск-ие , к-ое истинно тогда и только тогда, когда оба данных выск-ия имеют одинаковые значения, т.е. либо оба истинны, либо оба ложны.

2. Определение формулы алгебры выск-ий.1.Каждая пропозициональная переменная – есть формула;2.Если и - формулы алгебры выск-ий,то выражения также явл-ся формулами;3.Никаких других формул, кроме тех,к-ые образуются с помощью пунктов 1-2, нет.Замечание 1. Во всякой формуле число открывающихся скобок, очевидно, равно числу закрывающихся скобок. Скобки определяют порядок логических операций.

Замечание 2. Для простоты самые наружные скобки отбрасывают. Так что выражение в соответствии с принятым соглашением также считается формулой, хотя не удовлетворяет требованию опр-ия формулы.

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

Т.1. Логические значение составного выск-ия равно значению формулы на наборе логических значений составляющих выск-ий , т.е. .

Формула наз-ся выполнимой (опровержимой), если существует её истинная (ложная) конкретизация. Формула наз-ся тавтологией или тождественно истинной (противоречием или тождественно ложной), если любая её конкретизация истинна (ложна).

Т.2. Следующие формулы алгебры выск-ий явл-ся тавтологиями:1. - закон исключенного третьего.2. - закон отрицания противоречия.3. - закон двойного отрицания.4. - закон тождества. 5. - закон контрапозиции.6 - закон силлогизма.

7. - закон противоположности.8. - правило добавления антецедента («истина из чего угодно»). 9. - правило «из ложного что угодно». 10. - правило modus ponens.

11. - правило modus tollens.

12. - правило перестановки посылок.13. - правило объединения (и разъединения) посылок.14. - правило разбора случаев.15. - правило приведения к абсурду.16. - законы идемпотентности.

17. - законы упрощения.18. - законы коммутативности.19. , - з-ны ассоциативности.

20. , -з-ны дистрибутивности.

21. , - законы поглощения.

22. , - законы де Моргана.23. .

24 .

Т.3.(правило заключения, правило «модус поненс»). Если формулы и явл-ся тавтологиями, то формула также тавтология, т.е. из ╞ и╞ следует╞ .

Т.4. (правило подстановки). Если формула , содержащая пропозициональную переменную X, явл-ся тавтологией, то подста­новка в формулу вместо переменной X любой формулы Н снова приво­дит к тавтологии. Др-ми словами, из ╞ следует ╞ .Сл-ие:тавтологии обр-ют беск-ое мн-во.

3. Две формулы , , будем называть равносильными, если для любых конкретных выск-ий их конкретизации совпадают, т.е. = . обозначение .

Т.1. Две формулы и алгебры выск-ий равносильны тогда и только тогда, когда ф-ла явл-ся тавтологией: ╞ .

Д-во.а)необх-сть. Пусть . Тогда = для конкретных выск-ий . Предположим, что формула не явл-ся тавтологией. Тогда для любых . Отсюда следует, что . Значит . А это противоречит нашему предположению.Сл-но, явл-ся тавтологией.

б) дост-сть. Пусть ╞ . Тогда

для любых . Предположим, что . Тогда . Последнее означает, что . Это противоречит нашему предпол-ию.Значит, .

Сл-ие.Отн-ие равносильности между формулами алгебры выск-ий:

1.рефлексивно: ;

2.симметрично: если , то ;

3.транзитивно: если и , то , т.е.отн-ие равносильности явл-ся отн-ием эквивал-сти.Типичные равносильности: 1. , - коммутативность;

2. , - ассоциативность;

3. , - дистрибутивность;

4. , - идемпотентность;

5. , - закон поглощения;6. , - закон склеивания;

7. , - операция переменной с её инверсией;

8. , , , - операция с константами;

9. - закон двойного отрицания;

10. ;

11. Лемма(о замене). Если , то для любой ф-лы имеет место равносильность .4.Конъюнктивным одночленом от переменных наз-ся конъюнкция этих переменных или их отрицаний.

Дизъюнктивной одночленом от переменных наз-ся дизъюнкция этих переменных или их отрицаний. Дизъюнктивной нормальной формой наз-ся дизъюнкция конъюнктивных одночленов, т. е. выражение вида , где все , явл-ся конъюнктивными одночленами.

Конъюнктивной нормальной формой наз-ся конъюнкция дизъюнктивных одночленов , где все , явл-ся дизъюнктивными одночленами.

Т.1.Любая формула равносильными преобразованиями может быть приведена к дизъюнктивной нормальной форме (конъюнктивной нормальной форме).

1. , ; 2. , ;

3. , .Конъюнктивный (дизъюнктивный) одночлен называется совершенным, если в нем каждая переменная встречается один раз с отрицанием или без.Совершенный конъюнктивный одночлен имеет вид , а совершенный дизъюнктивный одночлен - .

Дизъюнктивная нормальная форма наз-ся совершенной, если в ней все конъюнктивные одночлены совершенны.

Конъюнктивная нормальная форма наз-ся совершенной, если в ней все дизъюнктивные одночлены совершенны.

Т.2. (о представлении формул алгебры выск-ий совершенными дизъюнктивными нормальными формулами). Каж­дая не тождественно ложная формула алгебры выск-ий имеет единственную совершенную дизъюнктивную нормальную форму с точностью до порядка следования конъ­юнктивных одночленов.

Т.3. (о представлении формул алгебры выск-ий совершенными конъюнктивными нормальными формулами). Каж­дая формула алгебры выск-ий, не являющиеся тавтологией, имеет единственную совершенную конъюнктивную нормальную форму с точностью до порядка следования дизъ­юнктивных одночленов.