Формулы алгебры высказываний. Виды формул

Пропозициональными переменными называются такие переменные, вместо которых можно подставлять конкретные высказывания. Эти переменные будем обозначать заглавными латинскими буквами: A, B, C, …, P₁, Q₁, X, Y, Z, X₁,…

Понятие формулы алгебры высказываний определяется следующим (индуктивным) образом:

а) всякая пропозициональная переменная есть формула;

б) если F₁ и F₂ – формулы, то выражения (ùF₁), (F₁ÙF₂), (F₁ÚF₂), (F₁®F₂), (F₁«F₂) также является формулами;

в) других формул, кроме построенных по правилам двух предыдущих пунктов, нет.

Договоримся в формулах опускать внешние скобки и все те скобки, которые становятся лишними, если логическим операциям приписать убывающие ранги в таком порядке: «, ®, Ú, Ù,ù.

Подформулой формулы называется всякая ее часть, которая сама является формулой.

Формула F(X₁, X₂, …X_n) называется выполнимой, если существует хотя бы один набор значений логических переменных Х₁, …, Х_n, при котором формула F(X₁, …,X_n) обращается в истинное высказывание

Формула F(X₁, X₂, …X_n) называется опровержимой, если существует хотя бы один набор значений логических переменных Х₁, …, Х_n, при котором формула F(X₁, X₂, …X_n) обращается в ложное высказывание.

Формула F(X₁, X₂, …X_n) называется тождественно ложной (или противоречием), если она обращается в ложное высказывание при любом наборе значений логических переменных.

Формула F(X₁, X₂, …X_n) называется тождественно истинной (или тавтологией, или законом логики), если она обращается в истинное высказывание при любом наборе значений логических переменных. Обозначение тавтологии: |= F(X₁, X₂, …, X_n).

Пусть дана некоторая формула F(X₁, X₂, …, X_n), и требуется найти все наборы значений логических переменных, при которых формула F принимает значение 1 (или значение 0). Будем записывать это так: F(X₁, X₂, …, X_n)=1 (F(X₁, X₂, …, X_n)=0) и говорить, что нужно решить логическое уравнение.