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

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

Так как смысл высказываний математическую логику не интересует, их вполне можно заменить переменными.

Пусть X, Y,…, Z,…, X_i, Y_i,…, Z_i – переменные, вместо которых можно подставить любые элементарные высказывания (или их значения истинности). Такие переменные называют пропозициональными или высказывательными переменными. С помощью высказывательных переменных и символов логических операций любое высказывание можно формализовать, т.е. заменить формулой, отражающей его логическую структуру.

Начнем с того, что уточним понятие формулы логики высказываний. Для этого зададим алфавит, т.е. набор символов, которые мы будем употреблять в логике высказываний:

1. Х, Y,…, Z,…, Xi, Yi,…, Zi (i – натуральное число) – символы для обозначения высказывательных переменных;

2. И, Л, 1, 0 – символы, обозначающие логические константы «истина» и «ложь»;

3. – символы логических операций;

4. (,), [, ] – скобки (вспомогательные символы, служащие для указания порядка выполнения операций).

Дадим теперь строгое определение формулы логики высказываний (будем говорить формула ЛВ):

1. Всякая высказывательная переменная – формула ЛВ.

2. Символы И, Л, 1, 0 – формулы ЛВ.

3. Если F – формула ЛВ, то – формула ЛВ.

4. Если F₁ и F₂ – формулы ЛВ, то , , и – формулы ЛВ.

5. Никаких других формул в логике высказываний нет.

Определение такого вида называется индуктивным. В п.п. 1 и 2 определены элементарные формулы, в п.п. 3 и 4 даны правила образования новых формул из любых двух данных формул.

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

Опишем процедуру формализации высказываний:

1. Если высказывание – простое, то ему ставится в соответствие элементарная формула.

2. Если высказывание – составное, то для составления соответствующей формулы нужно: а) выделить все элементарные высказывания и логические связки, образующие данное составное высказывание; б) заменить их соответствующими символами; в) расставить скобки в соответствии со смыслом данного высказывания.

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

1. Е = «Ваш приезд не является ни необходимым, ни желательным».

Составляющие простые высказывания: А = Ваш приезд необходим; В = Ваш приезд желателен. Они соединены между собой неявно имеющимся в высказывании Е союзом «и» и, кроме того, к каждому из них относится частица «не». Таким образом, форма сложного высказывания имеет вид:

2. Е = «Поиски врага длились уже три часа, но результатов не было, притаившийся враг ничем себя не выдал».

Переформулируем высказывание таким образом, чтобы выделить логические связки, неявно соединяющие простые высказывания: «Если притаившийся враг ничем себя не выдал, то его поиски длились уже три часа и результатов не было». Теперь можно выделить простые высказывания: А = Враг себя выдал; В = Поиски врага длились уже три часа и С = Результат был. Теперь можно формализовать сложное высказывание: .

Замечание: Символ импликации ставится там, где подразумевается вторая часть союза «если…, то…», т.е. на месте «то». Таким образом, формула, полученная во втором примере, читается: «Если не А, то В и не С».

3. Е = «Если число делится на 2 и на 3, то оно делится на 6».

В этом высказывании можно выделить следующие элементарные высказывания: А = Число делится на 2, В = Число делится на 3 и С = Число делится на 6. Тогда формула, соответствующая сложному высказыванию, имеет вид: .

Последний пример наглядно показывает, почему математическую логику интересует только логическая структура высказываний. Точно такую же логическую структуру, как в третьем примере имеет большое количество, например, математических теорем: «Если в четырехугольнике противоположные стороны параллельны и равны, то этот четырехугольник - параллелограмм» или «Если две прямые параллельны третьей прямой, то они параллельны друг другу» («Если и , то »).

Пример 9: По форме высказываний и выраженным на естественном языке составляющим его простым высказываниям получить фразу на естественном языке.

1. .

Составляющие простые высказывания:

А = Человек с детства давал нервам властвовать над собой.

В = Человек в юности давал нервам властвовать над собой.

С = Нервы привыкнут раздражаться.

D = Нервы будут послушны.

Для начала прочитаем формулу с использованием логических связок, не обращая внимания на смысл составляющих простых высказываний: «Если не А и не В, то не С и D». Теперь подставим вместо букв соответствующие высказывания, не произнося повторяющиеся части или заменяя их синонимами (местоимениями). Получим следующую фразу на естественном языке:

Е = Если человек с детства и юности своей не давал нервам властвовать над собой, то они не привыкнут раздражаться и будут ему послушны. (К.Д. Ушинский)

2. .

Составляющие простые высказывания:

А = Некто является врачом.

В = Больной поговорил с врачом.

С = Больному стало легче.

Фраза на естественном языке:

Е = Если больному после разговора с врачом не становится легче, то это не врач. (В.М. Бехтерев)

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

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

1) негация (отрицание); 2) конъюнкция; 3) дизъюнкция; 4) импликация и 5) эквиваленция.

Пример 10: Даны формулы. Определить порядок вычисления формул:

1. . Порядок вычисления следующий:

1) отрицание ; 2) конъюнкция ; 3) дизъюнкция ; 4) импликация и, наконец, эквиваленция .

2. . Порядок вычисления следующий:

1) отрицание ; 2) импликация ; 3) конъюнкция ; 4) дизъюнкция ; и 5) эквиваленция .

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

Число наборов значений, которые могут принимать п переменных, находится как 2^п.

Сформулируем алгоритм построения таблицы истинности сложного высказывания:

1. Вычислить количество строк и столбцов в таблице истинности.

Пусть в формуле п различных переменных и k операций. Переменные считаем каждую только один раз, а символы операций – все, сколько есть. Тогда число строк в таблице равно 2^п + 1 (число наборов значений переменных плюс строка заголовка), а число столбцов в таблице равно n + k.

2. Начертить таблицу.

3. Заполнить строку заголовка.

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

4. Заполнить оставшиеся строки таблицы, начиная с первого столбца.

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

Пример 11: Составить таблицы истинности для формул: 1) ; 2) .

1. . Эта формула содержит 2 различные переменные (К и С) и 4 символа логических операций, т.е. n = 2 и k = 4. Тогда строк в таблице 2² + 1 = 4 + 1 = 5, а столбцов – 2 + 4 = 6. Рисуем таблицу.

Определим порядок выполнения операций: 1) отрицание ; 2) дизъюнкция ; 3) конъюнкция и 4) импликация .

Заполняем строку заголовка, начиная с элементарных формул:

К	С

Заполняем первый столбик значениями истинности переменной К, для этого число пустых строк делим пополам (4: 2 = 2) и в половине пишем значение «истина», а в оставшейся половине – «ложь»:

Заполняем второй столбик значениями истинности переменной С. Для этого число пустых строк делим на 4 (4: 4 = 1) и попеременно записываем в строки по одному значению «истина» и «ложь» таким образом, чтобы каждому значению истинности переменной К соответствовали оба значения истинности переменной С:

К	С

Начиная с третьего столбика, заполняем строки результатами выполнения операций. В третьем столбике записываем результат выполнения операции отрицания . При этом смотрим на соответствующие значения переменной С:

К	С

В четвертом столбике записываем результаты выполнения дизъюнкции , обращая внимание на значения истинности переменных К и С в соответствующей строке:

В пятом столбике записываем результаты выполнения операции конъюнкции . При этом используем значения истинности соответствующих операций из третьего и четвертого столбиков:

И, наконец, в шестом столбике записываем результаты выполнения итоговой операции импликации , используя результаты предыдущей операции конъюнкции и значения истинности переменной К:

К	С

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

2. . Данная формула содержит 3 различные переменные и 4 символа логических операций. Число строк в таблице – 2³ + 1 = 8 + 1 = 9. Число столбцов – 3 + 4 = 7.

Определим порядок выполнения операций: 1) отрицание ; 2) отрицание ; 3) дизъюнкция и 4) эквиваленция . Нарисуем таблицу и заполним строку заголовка, начиная с элементарных формул:

А	В	С

Заполняем первый столбик значениями истинности переменной А, для этого число пустых строк делим пополам (8: 2 = 4) и в половине пишем значение «истина», а в оставшейся половине – «ложь»:

Заполняем второй столбик значениями истинности переменной В. Для этого число пустых строк делим на 4 (8: 4 = 2) и попеременно записываем в строки по одному значению «истина» и «ложь» таким образом, чтобы каждому значению истинности переменной А соответствовали по два значения истинности переменной В:

Заполняем третий столбик значениями истинности переменной С. Для этого число пустых строк делим на 8 (8: 8 = 1) и попеременно записываем в строки по одному значению «истина» и «ложь» таким образом, чтобы каждому значению истинности переменной В соответствовали оба значения истинности переменной С:

А	В	С

Заполняем четвертый столбик результатами выполнения операции отрицания . При этом смотрим, на значения истинности переменной В в соответствующих строках:

Аналогичным образом заполняем пятый столбик результатами операции отрицания . При этом смотрим на значения истинности переменной С в соответствующих строках:

А	В	С

В шестом столбике записываем результаты выполнения операции дизъюнкции . При этом используем значения истинности переменной А и результаты операции (первый и четвертый столбцы):

И, наконец, в седьмом столбике записываем результат выполнения итоговой операции эквиваленции . При этом используем результаты предыдущей операции и операции (шестой и пятый столбики):

А	В	С

Вывод следующий: истинность высказывания, имеющего данную логическую структуру, зависит от значений истинности составляющих его элементарных высказываний.

Дата добавления: 2014-01-06