Формулы алгебры логики

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

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

Определение 2. Формула , принимающая ложное значение при любых комбинациях значений входящих в нее высказываний, называются тождественно ложной (ТЛФ) и записывается .

Например: - ТИФ, - ТЛФ.

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

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

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

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

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

2. Считается, что знак операции конъюнкции связывает высказывания формулы “сильнее” знаков т.е. вместо пишем , вместо пишем , и вместо пишем .

3. Считается, что знак связывает высказывания сильнее, чем знаки и , т.е. вместо можно писать , а вместо можно писать .

4. Считается, что знак сильнее связывает высказывания, чем знак , т.е. вместо пишем .

5. Можно опускать внешние скобки, которые содержат внутри себя остальные символы, составляющие формулу. Так, формулу можно писать .

Приведенные соглашения значительно упрощают запись формулы. Так, например, формула записанная с

учетом сказанного выше, будет выглядеть так .

При чтении формулы её название определяется последней операцией, наименее приоритетной из всех остальных операций, входящих в формулу. Так, приведенная выше формула представляет собой импликацию, так как последняя операция есть импликация, выполняемая по очереди шестой.

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

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

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

Количество столбцов таблицы истинности определяется суммой чисел последовательно выполняемых операций и простых высказываний.

Рассмотрим пример. Составить таблицу истинности для сложного высказывания

Выполним сначала разметку заданной формулы. В результате получим . Так как простых высказываний 3, то число строк в таблице истинности будет , и число столбцов тоже будет .

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

Поэтому в таблице истинности для наглядности удобно все первые столбцы пометить символами высказываний (x,y,z,…), а все последующие – номерами операций в возрастающем порядке и соответствующими им высказываниями, над которыми выполняется данная операция. Таким образом, таблица истинности для данного примера будет иметь вид

Таблица 6.

Таблица истинности для формулы

			(1)	(2)	(3)	(4)	(5)

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

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