Главная | Обратная связь

Формулы и их логические возможности.

Будем считать, что существуют некоторое множество элементарных высказываний. Их, как правило обозначают первыми буквами латинского алфавита, а также 0 и 1. введем в рассмотрение высказывательные переменные - символы, вместо которых можно подставить высказывания. высказывательные переменные обозначают, как правило, последними буквами латинского алфавита (x, y, z, …)также введены знаки (обозначения) логических операций. Введем еще два служебных символа: «(« - открывающая скобка и «)» - закрывающая скобка.

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

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

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

2. Если A и B – формулы, то , есть формулы.

3. Других формул алгебры высказываний нет.

Логической возможностью формулы Ф[1] от переменных A₁, A₂, …, A_n называется набор конкретных значений истинности для переменных A₁, A₂, …, A_n. Таблица, содержащая перечень всевозможных логических возможностей формулы Ф, вместе с указанием значений Ф в каждой логической возможности, называется таблицей истинности этой формулы.

Пример. Всякая простая формула, состоящая из одной переменной, имеет две логические возможности: 0 и 1. всякая формула от двух букв имеет четыре логические возможности: (0,0), (0,1), (1,0), (1,1).

Формула называется тождественно истинной (тождественно ложной), если она принимает лишь значение 1 (0) при любых логических возможностях входящих в нее переменных. Тождественно истинные формулы называются тавтологиями, тождественно ложные – противоречиями. Этот факт обозначается следующим образом: Фº1 или Фº0.

Две формулы называются равносильными, если на всех одинаковых наборах переменных значения этих формул совпадают. Равносильность формул A и B обозначают A º B.

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