logo
методичка мат лог

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

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

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

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

б) если F1 и F2 – формулы, то выражения (F1), (F1F2), (F1F2), (F1F2), (F1F2) также является формулами;

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

Договоримся в формулах опускать внешние скобки и все те скобки, которые становятся лишними, если логическим операциям приписать убывающие ранги в таком порядке: , , , ,.

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

Формула F(X1, X2, …Xn) называется выполнимой, если существует хотя бы один набор значений логических переменных Х1, …, Хn, при котором формула F(X1, …,Xn) обращается в истинное высказывание

Формула F(X1, X2, …Xn) называется опровержимой, если существует хотя бы один набор значений логических переменных Х1, …, Хn, при котором формула F(X1, X2, …Xn) обращается в ложное высказывание.

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

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

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