1. Символы исчисления высказываний и определение формулы исчисления высказываний.

отрицание (инверсия), конъюнкция (от лат. conjunctio – союз, связь; логическое умножение), дизъюнкция (от лат. disjunctio – различие, разделение; логическое сложение), импликация (от лат.implico – тесная связь), и эквиваленция (от лат. aequivalens – равносильный, равноценный).

Отрицанием х называется новое высказывание которое является истинным, если высказывание ложно, и ложным если высказывание x истинно. Высказывание читается как “не ” или “неверно, что ”. Логическое значение высказывания можно выразить с помощью таблицы истинности.

Конъюнкцией двух высказываний называется новое высказывание, которое считается истинным, если оба высказывания и истинны, и ложным, если хотя бы одно из них ложно. Конъюнкция высказываний обозначается &, или , или или и читается “ и ”.

Дизъюнкцией двух высказываний называется новое высказывание, которое считается истинным, если хотя бы одно из высказываний истинно, и ложным, если они оба ложны. Дизъюнкция обозначается или и читается “ или ”.

Импликацией двух высказываний называется новое высказывание, которое считается ложным, если истинно, а – ложно, и истинным во всех остальных случаях. Импликация высказываний обозначается и читается “если то”, или “из следует ”, или “ влечет ”. Высказывание называют условием или посылкой, высказывание – следствием или заключением, а общее высказывание _¯ следованием или импликацией, или условным высказыванием.

Эквиваленцией (эквивалентностью) двух высказываний называется новое высказывание, которое считается истинным, когда оба высказывания либо одновременно истинны, либо одновременно ложны, и ложным – во всех остальных случаях.

Эквиваленция высказываний обозначается

Всякое сложное высказывание, которое получается из простых путем применения приведенных выше операций, называется формулой исчисления высказывания. Для сокращения записей обозначают формулы большими буквами латинского алфавита: и т.д.

2. Определение доказуемой формулы и система аксиом исчисления высказываний.

Исчисление высказываний опирается на 11 аксиом и 2 простейших правила вывода. Все аксиомы являются правильными сложными высказываниями. Они разделены на 4 группы.

Система аксиом исчисления высказываний

Первая группа аксиом:

I₁

I₂

Вторая группа аксиом:

II

II

II

Третья группа аксиом:

II

II

II Четвертая группа аксиом:

IV

IV

IV

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

а) всякая аксиома является доказуемой формулой;

б) формула, полученная из доказуемой формулы путем применения правила подстановки, есть доказуемая формула;

в) формула , полученная из доказуемых формул и путем применения правила заключения, есть доказуемая формула;

г) никакая другая формула исчисления высказываний не считается доказуемой.

Процесс получения доказуемых формул называют доказательством.