Логические формулы. 
Основы математической обработки информации

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

Аналогично в логике составляются выражения из простых высказываний и знаков логических операций. Эти выражения называют формулами.

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

Формулы обычно обозначают большими буквами греческого алфавита, указывая, какие высказывания в них входят. Например, ЧДА, В) обозначает логическую формулу, в которую входят два простых высказывания.

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

Пример 4.3.

Рассмотрим сложное высказывание: «Если на этой недели я получу стипендию и зарплату за работу в летнем лагере, то куплю маме диск с ее любимым фильмом или себе билет на балетный спектакль». В данном предложении можно выделить несколько логических связок (они выделены в тексте), которые обозначают три логические операции. Кроме того, можно выделить четыре высказывания: А — «на этой неделе я получу стипендию»; В — «на этой неделе я получу зарплату за работу в летнем лагере; С — «куплю маме диск с ее любимым фильмом»; D — «куплю себе билет на балетный спектакль». Таким образом, получаем следующую формулу: А д В —> С v D.

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

В приведенной в примере формуле сначала выполняются конъюнкция и дизъюнкция по порядку, а затем импликация.

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

Приведем пример построения таблицы истинности формулы —Л vS-> -> С:

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

Рассмотрим две формулы относительно одних и тех же простых высказываний.

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

Пример 4.4.

Проверим равносильность следующих формул: Ф (Л, В) = (Л —> В) д (В —> Л) и Ч^Л, В) = Л В.

Решение

Строим таблицу истинности:

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

Равносильность формул записывается с помощью значка: Ф (Л, В)

чдл, в).

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

Понятие равносильности используется и при рассмотрении предикатов.

Определение 4.12. Два предиката Р (х_[у х₂,…, х_п) и Q (x_{y х₂, …, х") называются равносильными, если при одинаковых значениях истинности переменных они становятся высказываниями, принимающими одинаковые значения истинности. Для обозначения равносильных предикатов используют тот же значок, что и для равносильных формул: Р Q.

Равносильностью предикатов вы пользовались в школе при решении уравнений и неравенств. Ведь сам процесс решения состоит в замене одного предиката равносильным ему, но более простого вида.

Убедитесь в этом, проанализировав решение следующего неравенства:

х² — Ъх + 2 < 2х — 4 х² — 5х + б < 0 (х — 2)(х — 3) < 0 (х — 2 < О и х — 3 > 0) или (х — 2 > 0 и х — 3 < 0) «(х < 2 и х > 3) или (х>2икЗ) 0 или (х > 2 и х < 3) (х > 2 и х < 3). В математике получившуюся конъюнкцию обычно записывают в виде двойного неравенства 2 < х < 3.