Алгебра логики
Как часто поведение котов вам кажется странным? А если кот в галстуке или вооружен? Сейчас будем разбираться в логике с помощью этих пушистых созданий.
Понятие алгебры логики
Обратите внимание на этого персонажа:
Я скажу про него две вещи:
- Этот кот в галстуке.
- Этот кот белого цвета.
Очевидно, что с первым высказыванием и поспорить нельзя, а вот второе — наглая ложь. А если я захочу вас запутать: «Этот кот в галстуке или он белого цвета, из чего следует, что он белого цвета и в галстуке или не белый». Что это в итоге — правда или ложь?
Чтобы это определить, в математике есть отдельный раздел.
Алгебра логики — это раздел математики, который занимается логическими операциями над высказываниями.
Любое высказывание может быть либо истинным, либо ложным. Цель алгебры логики — определять истинность логических выражений на основании отдельных высказываний. Алгебра логики действительно может, например, складывать и умножать высказывания друг с другом, и чтобы в записи это выглядело адекватно, истину принято обозначать как 1, а ложь — как 0.
Логические выражения и операторы
Как вычислить истинность логического выражения?
Термин высказывание, мы теперь знаем. Но что такое логическое выражение? Выражение — это уравнение из высказываний, как математическое уравнение из чисел.
«Этот кот вооружен и его глаза зеленого цвета», — в одном выражении мы использовали два высказывания.
Истинность выражения определяется истинностью логических высказываний, а также логическими операторами, которые стоят между ними.
Например, я скажу про того же самого кота: «Этот кот вооружен и его глаза голубые». Это будет наглая ложь, так как я употребил союз И, то есть подразумеваю, что оба высказывания истинны — что неправда. Но если бы я сказал: «Этот кот вооружен или его глаза голубые», союз ИЛИ защитил бы меня от клейма лжеца. Я делаю акцент на истинности только одного высказывания из двух.
Так и работают логические операторы — в зависимости от них все выражение и принимает значение истины или лжи.
Основные логические операторы алгебры логики:
-
Конъюнкция: логическое умножение или логическое И. В записи обозначается как ∧. А ∧ В дает истину только в том случае, если оба высказывания А и В истинны.
Называется логическим умножением, потому что имеет схожий принцип работы: если хоть один из множителей будет равен 0, все выражение будет равно 0.
Называется логическим сложением за схожесть: если складывать только 0 и 1, чем мы и занимаемся, то достаточно одному слагаемому быть 1, чтобы все выражение не было равно 0.
Важно сразу понять — если применить логическое сложение к двум единицам (1 ∨ 1), мы получим не 2, а все еще 1. Все-таки единица здесь означает не число, а истину, и сложив две, мы не получим одну сверх-истину.
Приоритет этих операторов:
- инверсия;
- конъюнкция;
- дизъюнкция;
- импликация;
- эквиваленция.
Как и везде в математике, приоритет можно менять с помощью скобок — что в них, то выполняется в первую очередь.
Таблицы истинности
В логических уравнениях высказывания используются в виде переменных, а главная проблема, которую рассматривает алгебра логики — когда точно неизвестна истинность каждого высказывания. Назовем эту ситуацию “кот в мешке”. Сказать про кота можно что угодно, но будет ли это правдой — мы не узнаем, пока не заглянем в мешок. В таких ситуациях нам может помочь таблица истинности.
Таблица истинности — это таблица, которая показывает истинность всего логического уравнения в зависимости от истинности отдельных переменных.
В этой таблице содержатся все возможные наборы переменных. Количество наборов N зависит от количества различных переменных i как N = 2 i .
Чтобы удобно записать наборы, нумеруем их по порядку начиная с 0, переводим их номер в двоичную систему счисления (2сс) и записываем набор цифр.
Давайте запишем таблицы истинности для известных нам логических операторов:
- инверсия берет только 1 переменную и сразу меняет ее значение:
- конъюнкция берет две переменные и возвращает 1 только в том случае, если обе равны 1:
- дизъюнкция вернет 1, если хотя бы одна из переменных равна 1:
- эквиваленция вернет 1, если переменные равны, и 0 в противном случае:
- импликация вернет 0, если из истины будет следовать ложь, и 1 во всех остальных случаях:
| Импликацию можно выразить через дизъюнкцию: А ⇒ В = ¬А ∨ В |
Зная таблицы истинности отдельных операторов, давайте попробуем составить таблицу истинности для полного выражения.
Например, для выражения: А ∧ (В ∨ С) ≡ В ⇒ ¬А.
Важно правильно расставить порядок операций. Как и всегда, в первую очередь выполняется действие в скобках, а дальше — в порядке приоритета.
Здесь порядок операций будет следующим:
Создадим таблицу, в которой сразу пропишем все наборы 0 и 1 для переменных А и В и добавим столбцы для каждого шага вычисления.
Чтобы удобно записать наборы, пронумеруем их по порядку начиная с 0. Переведем их номер в 2сс и запишем набор цифр. У нас 3 различные переменные, поэтому должно быть 8 наборов.
- Первое действие — сложение В и С. Для каждого набора запишем результат сложения в соответствующий столбец.
- Второе действие — инверсия переменной А.
- Третье действие — умножение значения А на результат первого действия:
- Четвертое — импликация значения В и результата второго действия:
- И последнее действие — эквиваленция результатов 3 и 4 действий:
Последний столбец — и есть результат таблицы истинности. По нему можно сказать, что при А = 1, В = 0 и С = 1 все исходное выражение равно 1, а во всех остальных случаях — 0.
Законы логики
Их не так уж и мало: от самых простых и очевидных до достаточно хитрых; от тех, которые встречаются очень часто до довольно редких.
Не обязательно знать все наизусть — часть из них действительно проста и похожа на правила математики начальной школы. Про остальные стоит помнить: если увидите очень большое логическое уравнение, высока вероятность того, что эти законы помогут его сократить.
Попробуем упростить исходное выражение ¬(¬А ∧ ¬В) ∨ В ∧ С:
- Первым можно увидеть закон де Моргана, где у нас идет отрицание целой скобки:
¬(¬А ∧ ¬В) ∨ В ∧ С = ¬(¬А) ∨ ¬(¬В) ∨ В ∧ С
- Здесь же появляются переменные А и В, к которым можно применить закон двойного отрицания:
¬(¬А) ∨ ¬(¬В) ∨ В ∧ С = А ∨ В ∨ В ∧ С
- Можно заметить закон поглощения — В складывается с умножением В на С:
А ∨ В ∨ В ∧ С = А ∨ В
Итого, уравнение с 3 переменными и множеством отрицаний мы смогли превратить в максимально простую запись, где осталось всего 2 переменные:
¬(¬А ∧ ¬В) ∨ В ∧ С = А ∨ В
Фактчек
- Алгебра логики — это математика, которая пользуется не числами, а высказываниями, являющимися истинными или ложными. Истина обозначается как 1, а ложь — как 0.
- Основными логическими операторами являются инверсия, конъюнкция, дизъюнкция, импликация и эквиваленция.
- Для расчета истинности логического уравнения используется таблица истинности.
- Законы логики помогают сокращать логические уравнения.
Проверь себя
Задание 1.
Выберите правильный порядок приоритета логических операторов:
- Импликация, эквиваленция, конъюнкция, дизъюнкция, инверсия.
- Инверсия, конъюнкция, дизъюнкция, импликация, эквиваленция.
- Инверсия, конъюнкция, дизъюнкция, эквиваленция, импликация.
- Инверсия, дизъюнкция, конъюнкция, эквиваленция, импликация.
Задание 2.
Сопоставьте название логического оператора с упрощенным:
| Инверсия | А. Умножение |
| Эквиваленция | Б. Отрицание |
| Импликация | В. Следование |
| Дизъюнкция | Г. Равенство |
| Конъюнкция | Д. Сложение |
Задание 3.
Чему будет равен последний столбец таблицы истинности для уравнения: А ∨ В ⇒ ¬С?
- 11101010
- 11101111
- 11111110
- 11000100
Задание 4.
Сократите логическое выражение: ¬(А ∨ В) ∧ (¬А ∨ С)
- ¬(А ∧ В)
- ¬А ∨ ¬В ∨ С
- ¬А ∧ ¬В ∧ С
- ¬А ∧ ¬В
Ответы: 1. — 2; 2. — 1Б, 2Г, 3В, 4Д, 5А; 3. — 1; 4. — 4.
Логические операции и их свойства
Конъюнкция или логическое умножение (в теории множеств – это пересечение)
Конъюнкция является сложным логическим выражением, которое истинно в том и только том случае, когда оба простых выражения являются истинными. Такая ситуация возможно лишь в единственном случае, во всех остальных случаях конъюнкция ложна.
Обозначение: &, $\wedge$, $\cdot$.
Таблица истинности для конъюнкции
- Если хотя бы одно из подвыражений конъюнкции ложно на некотором наборе значений переменных, то и вся конъюнкция будет ложной для этого набора значений.
- Если все выражения конъюнкции истинны на некотором наборе значений переменных, то и вся конъюнкция тоже будет истинна.
- Значение всей конъюнкции сложного выражения не зависит от порядка записи подвыражений, к которым она применяется (как в математике умножение).
Дизъюнкция или логическое сложение (в теории множеств это объединение)
Дизъюнкция является сложным логическим выражением, которое истинно практически всегда, за исключением, когда все выражения ложны.
Таблица истинности для дизъюнкции
- Если хотя бы одно из подвыражений дизъюнкции истинно на некотором наборе значений переменных, то и вся дизъюнкция принимает истинное значение для данного набора подвыражений.
- Если все выражения из некоторого списка дизъюнкции ложны на некотором наборе значений переменных, то и вся дизъюнкция этих выражений тоже ложна.
- Значение всей дизъюнкции не зависит от порядка записи подвыражений (как в математике – сложение).
Отрицание, логическое отрицание или инверсия (в теории множеств это отрицание)
Отрицание — означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО и в итоге получаем, что если исходное выражение истинно, то отрицание исходного – будет ложно и наоборот, если исходное выражение ложно, то его отрицание будет истинно.
Обозначения: не $A$, $\bar$, $¬A$.
Таблица истинности для инверсии
«Двойное отрицание» $¬¬A$ является следствием суждения $A$, то есть имеет место тавтология в формальной логике и равно самому значению в булевой логике.
Импликация или логическое следование
Импликация — это сложное логическое выражение, которое истинно во всех случаях, кроме как из истины следует ложь. То есть, данная логическая операция связывает два простых логических выражения, из которых первое является условием ($A$), а второе ($A$) является следствием условия ($A$).
Обозначения: $\to$, $\Rightarrow$.
Таблица истинности для импликации
- $A \to B = ¬A \vee B$.
- Импликация $A \to B$ ложна, если $A=1$ и $B=0$.
- Если $A=0$, то импликация $A \to B$ истинна при любом значении $B$, (из лжи может следовать истинна).
Эквивалентность или логическая равнозначность
Эквивалентность — это сложное логическое выражение, которое истинно на равных значениях переменных $A$ и $B$.
Обозначения: $\leftrightarrow$, $\Leftrightarrow$, $\equiv$.
Таблица истинности для эквивалентности
- Эквивалентность истинна на равных наборах значений переменных $A$ и $B$.
- КНФ $A \equiv B = (\bar \vee B) \cdot (A \cdot \bar)$
- ДНФ $A \equiv B = \bar \cdot \bar \vee A \cdot B$
Строгая дизъюнкция или сложение по модулю 2 ( в теории множеств это объединение двух множеств без их пересечения)
Строгая дизъюнкция истинна, если значения аргументов не равны.
Для функции трёх и более переменных результат выполнения операции будет истинным только тогда, когда количество аргументов равных $1$, составляющих текущий набор — нечетное. Такая операция естественным образом возникает в кольце вычетов по модулю 2, откуда и происходит название операции.
Обозначения: $A \oplus B$ (в языках программирования), $A≠B$, $A \wedge B$ (в языках программирования).
Таблица истинности для операции сложения по модулю два
Свойства строгой дизъюнкции:
- $a \oplus 0 = a$(идемпотентность)
- $a \oplus 1 = \bar$(отрицание)
- $a \oplus a = 0$(получение 0)
- $a \oplus b = b \oplus a$(коммутативность)
- $(a \oplus b) \oplus c = a \oplus (b \oplus c)$(ассоциативность)
- $(a \oplus b) \oplus b = a$(поглощение)
- $\bar \oplus b = a \oplus \bar = (a \equiv b)$(сравнения по модулю)
Стрелка Пирса
Бинарная логическая операция, булева функция над двумя переменными. Названа в честь Чарльза Пирса и введена в алгебру логики в $1880—1881$ гг.
Обозначения: $\downarrow$ , ИЛИ-НЕ
Таблица истинности для стрелки Пирса
Стрелка Пирса, как и конъюнкция, дизъюнкция, отрицание, образует базис для булевых функций двух переменных. При помощи стрелки Пирса, можно построить все остальные логические операции, например:
$X \downarrow X = ¬X$— отрицание
$(X \downarrow Y) \downarrow (X \downarrow Y) \equiv X \vee Y$ — дизъюнкция
$(X \downarrow X) \downarrow (Y \downarrow Y) \equiv X \wedge Y$ — конъюнкция
$((X \downarrow X) \downarrow Y) \downarrow ((X \downarrow X) \downarrow Y) = X \to Y$ — импликация
В электронике стрелка Пирса представлена в виде элемента, который носит название «операция 2ИЛИ-НЕ» (2-in NОR).
Штрих Шеффера
Булева функция двух переменных или бинарная логическая операция. Введена в рассмотрение Генри Шеффером в 1913 г.
Обозначения: $|$, эквивалентно операции И-НЕ.
Таблицей истинности для функции штрих Шеффера
Штрих Шеффера образует базис для всех булевых функций двух переменных. Применяя штрих Шеффера можно построить остальные операции, например,
$X \mid X = ¬X$ — отрицание
$(X \mid Y) \mid (X \mid Y) = (X \wedge Y)$ — конъюнкция
$(X \mid X) \mid (Y \mid Y) = X \vee Y$ — дизъюнкция
Для электроники это означает, что реализация схем возможна с использованием одного типового элемента (правда это дорогостоящий элемент).
Порядок выполнения логических операций в сложном логическом выражении
- Инверсия(отрицание);
- Конъюнкция (логическое умножение);
- Дизъюнкция и строгая дизъюнкция (логическое сложение);
- Импликация (следствие);
- Эквивалентность (тождество).
Для того чтобы изменить указанный порядок выполнения логических операций, необходимо использовать скобки.
Общие свойства
Для набора из $n$ логических переменных существует ровно $2^n$ различных значений. Таблица истинности для логического выражения от $n$ переменных содержит $n+1$ столбец и $2^n$ строк.
Что такое дизъюнкция и конъюнкция
Формулы алгебры высказываний состоят из высказываний, соединенных связками. Каждое высказывание – это повествовательное предложение, о котором в данной ситуации можно сказать, что оно истинно или ложно, но не то и другое одновременно. В качестве связок используют операции над высказываниями: конъюнкция, дизъюнкция, отрицание, импликация, эквиваленция.
Синтаксически формула алгебры высказываний – это логическое выражение. Семантически оно задает булеву функцию $n$ переменных, где $n$ – число простых высказываний, входящих в формулу. Каждая переменная в формуле может принимать одно из двух значений: истина (1) и ложь (0). Выражаемая функция на всяком наборе значений переменных также принимает одно из двух значений. Всего число всех возможных булевых функций от $n$ переменных равно числу способов $n$ раз выбрать 0 или 1. Изобразив дерево полного перебора, увидим, что это полное двоичное дерево высоты $n$, каждый лист которого соответствует $n$-мерному двоичному вектору. Поэтому всего в нем $2^n$ листьев. Итак, число всех возможных булевых функций от $n$ переменных равно $2^n$.
Любую булеву функцию можно задать ее таблицей истинности.
| $A$ | $B$ | $A \& B$ | $A \vee B$ | $A \to B$ |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 |
Если в формуле не расставлены скобки, операции выполняются в таком порядке: $\neg$, $\&$, $\vee$, $\to$.
Формула алгебры логики называется выполнимой, если существует набор значений переменных, на которых реализуемая ею функция принимает значение 1, и опровержимой, если 0. Формула называется тождественно истинной или тавтологией, если она реализует функцию “тождественная единица”, и тождественно ложной, если 0.
Эквивалентность формул АВ
Формулы $\varphi(x_1, x_2, \dots, x_n)$ и $\psi(x_1, x_2, \dots, x_n)$ называются эквивалентными, если совпадают их таблицы истинности, т.е. на любом наборе значений переменных $x_1, x_2, \dots, x_n$ обе формулы принимают одинаковые значения.
Приведем основные эквивалентности между формулами.
1) $xy = yx$, $x \vee y = y \vee x$ (коммутативность $\&$ и $\vee$);
2) $(xy)z = x(yz)$, $(x \vee y) \vee z = x \vee (y \vee z)$ (ассоциативность $\&$ и $\vee$);
3) $x(y\vee z) = xy \vee xz$ (дистрибутивность $\&$ относительно $\vee$), $x \vee (y \& z) = (x \vee y) \& (x \vee z)$ (дистрибутивность $\vee$ относительно $\&$);
4) $\neg (x \& y) = \neg x \vee \neg y$, $\neg (x \vee y) = \neg x \& \neg y$ (законы двойственности де Моргана);
5) $xy \vee x\&\neg y = x$, $(x \vee y)(x \vee \neg y) = x$ (правила склеивания);
6) $x \vee (xy) = x$, $x(x \vee y) = x$ (правила поглощения);
7) $(xz) \vee (y\& \neg z) = (xz) \vee (y \neg z) \vee (xy)$ (правило обобщенного склеивания);
8) $x \& x = x$, $x \vee x = x$ (законы идемпотентности);
9) $x \& 0 = 0$, $x \vee 0 = x$, $x \& 1 = x$, $x \vee 1 = 1$, $(x \Rightarrow 0) = \overline x$, $(x \Rightarrow 1) = 1$ (свойства относительно констант);
10) $x \vee \neg x = 1$ (закон исключенного третьего);
11) $x \& \neg x = 0$ (закон противоречия);
12) $\neg\neg x = x$ (закон двойного отрицания);
13) $x \to y = \neg x \vee y$ (замена импликации);
14) $x \vee (\neg x \& y) = x \vee y$, $\neg x \vee (x \& y) = \neg x \vee y$;
15) $x \& (\neg x \vee y) = x \& y$, $\neg x \& (x \vee y) = \neg x \& y$.
Дизъюнктивные и конъюнктивные нормальные формы АВ
Чтобы определить, равносильны ли формулы (являются ли они тождественными), необходимо привести их к нормальной форме [Волкова]. В нормальной форме присутствуют только простые логические операции, и отрицание относится только к элементарным высказываниям.
ДНФ – это дизъюнкция элементарных конъюнкций (конъюнктов), КНФ – это конъюнкция элементарных дизъюнкций (дизъюнктов). Элементарная дизъюнкция (конъюнкция) – это дизъюнкция (конъюнкция) переменных и их отрицаний, в которую каждая переменная входит не более одного раза.
Теорема. Для любой формулы $A$ существует равносильная формула $B$, находящаяся в КНФ (ДНФ), и причем не одна.
Чтобы привести формулу к ДНФ, нужно: 1) выразить импликацию по формуле замены импликации, 2) используя законы де Моргана, перенести все отрицания к переменным и сократить двойные отрицания, 3) используя закон дистрибутивности $\&$ относительно $\vee$, преобразовать формулу так, чтобы все конъюнкции выполнялись раньше дизъюнкций.
Совершенные дизъюнктивные и конъюнктивные нормальные формы
В СДНФ (СКНФ) формула приведена к ДНФ (КНФ), и все слагаемые (множители) формулы $A$ попарно различны, причем каждая переменная входит в каждое слагаемое (множитель) ровно один раз.
Теорема. Каждая не тождественно истинная формула имеет единственную СКНФ.
Теорема. Каждая не тождественно ложная формула имеет единственную СДНФ.
Правило перехода от ДНФ (КНФ) к СДНФ (СКНФ) можно прочитать в [Волкова, с. 11].
Чтобы по таблице истинности записать СДНФ или СКНФ, заметим, что всякий конъюнкт, содержащий все переменные, в котором каждой 1 соответствует переменная, а 0 – переменная с отрицанием, принимает истинное значение только в одной строчке. Поэтому дизъюнкция таких конъюнктов по строчкам, в которых функция принимает истинное значение, и даст выражение для этой функции.
Аналогично строится СКНФ: дизъюнкт, в котором присутствуют переменные с отрицаниями (1 соответствует переменная с отрицанием, 0 – переменная) будет ложным в этой и только этой строчке. Тогда если мы запишем конъюнкцию таких дизъюнктов по строчкам с 0, то она будет принимать значение “ложь” во всех этих строчках и “истина” в остальных строчках таблицы истинности.
Для минимизации ДНФ применяют метод Блейка [Волкова], метод Квайна, карты Карно, а также метод неопределенных коэффициентов [Гринченков, с. 28], который реализуется на ЭВМ. См. [Белоусов, с. 408].
Логическое следствие
Основная задача логики в нахождении общих способов установления связей логических значений одних высказываний с логическими значениями других высказываний на основании исследования формальной структуры высказываний. Это служит средством систематизации знаний. [Игошин, с. 53]
Задача математической логики в вопросах логического следования состоит в том, чтобы указать такие формы высказываний $A_1, A_2, \dots, A_m, B$, когда последнее высказывание непременно было бы следствием $m$ первых, независимо от конкретного содержания всех этих высказываний.
Пусть даны формулы $A_1, \dots, A_m, B$, которые зависят от переменных $X_1, \dots, X_n$. Формула $B$ называется логическим следствием формул $A_1, \dots, A_m$, если, при истинности одновременно всех формул $A_1, \dots, A_m$ истинна и формула $B$ при одних и тех же значениях переменных $X_1, \dots, X_n$. [Волкова]
Для логического следствия используют запись $A_1, \dots, A_m \models B$ или $\dfrac
Справедлив следующий критерий следования [Волкова, с. 29]: не тождественно истинная формула $B$ является логическим следствием формул $A_1, \dots, A_m$, не все из которых тождественно истинны, когда все множители формулы $B$, находящейся в СКНФ, входят в СКНФ формулы $A_1, \dots, A_m$.
Чтобы найти все (неравносильные) формулы, являющиеся логическими следствиями из предпосылок $A_1, \dots, A_m$, необходимо выполнить следующие действия:
1) составить конъюнкцию $A_1\cdot \dots\cdot A_m$.
2) найти СКНФ формулы $A_1\cdot \cdot A_m$;
3) выписать все множители найденной СКНФ, а также всевозможные конъюнкции этих множителей.
Полученные формулы являются логическими следствиями предпосылок $A_1, \dots, A_m$.
Теорема (признак логического следствия). [Игошин, с. 56] Формула $G$ будет логическим следствием формулы $F$ тогда и только тогда, когда формула $F \to G$ является тавтологией: \(F \models G \Leftrightarrow \models F \to G.\)
Замечание. [Игошин, с. 58] Если некоторая формула является тавтологией, то и всякое ее логическое следствие также является тавтологией: \(\models F \text < \;и\; >F \models G \;\Rightarrow\; \models G.\)
Для проверки формул на логическое следование можно использовать метод от противного [Игошин, с. 59], см. также онлайн-курс на Stepik.
Метод резолюций
Метод резолюций – это правило вывода логических формул, которое применяется для автоматического доказательства теорем.
Правило резолюции имеет следующий вид [Игошин, с. 60]: \(G \vee F, \; H \vee \neg F \;\; \models \;\; G \vee H.\)
Нетрудно проверить, что формула $G \vee H$ действительно является логическим следствием двух формул, стоящих слева. При этом говорят, что формула $G \vee F$ резольвирует с формулой $H \vee \neg F$, формула $G \vee H$ называется резольвентой формул $G \vee F$ и $H \vee \neg F$ (по переменной $F$), и пишут $G \vee H = <\rm Res>_F(G \vee F, H \vee \neg F)$.
Если при этом в условии отсутствует формула $G$ (или она тождественно ложна), то правило принимает следующий вид: \(F, \; H \vee \neg F \;\; \models \;\; H,\) представляющий известное правило modus ponens: $F, F \to H \; \models \; H$.
Если же отсутствует формула $H$, то правило принимает следующий вид: \(G \vee F, \; \neg F \;\; \models \;\; G.\)
Рассмотрим посылки правила резолюции: $G \vee F$, $H \vee \neg F$. По формуле замены импликации можно представить их в виде $\neg G \to F$, $F\to H$. Отсюда по правилу цепного заключения получим $\neg G \to H$, или $G \vee H$. Итак, мы доказали, что $G \vee F, \; H \vee \neg F \;\; \models \;\; G \vee H$, т.е. правило резолюции.
Метод резолюций, основанный на правиле резолюции, проверяет формулы алгебры высказываний на логическое следование. [Игошин, с. 61; Волкова, с. 42]
Перевод с естественного языка на язык математической логики
Перевод высказывания естественного языка в символический вид называется его формализацией. Формула логики высказываний сама по себе не имеет никакого содержания. В частности, она не является ни истинной, ни ложной. Она превращается в высказывание, истинное или ложное, при всякой подстановке вместо всех ее пропозициональных переменных любых конкретных высказываний. Такой процесс подстановки называется интерпретацией данной формулы алгебры высказываний. [Игошин, с. 30].
Рассмотрим пример из логического теста. Дано высказывание: “пуфелки зелёные или йцукенги розовые”. Требуется из набора высказываний выбрать те, которые из него следуют:
1) если пуфелки не зелёные, то йцукенги розовые
2) если пуфелки зелёные, то йцукенги розовые
3) неправда, что пуфелки не зелёные и йцукенги розовые
4) йцукенги розовые или пуфелки зелёные
5) если пуфелки не зелёные, то йцукенги не розовые
6) неправда, что пуфелки не зелёные и йцукенги не розовые
Обозначим $A$ = “пуфелки зеленые”, $B$ = “йцукенги розовые”. Исходное высказывание можно переписать в виде $A \vee B$.
Требуется выбрать из следующих высказываний тавтологии:
1) $A \vee B \; \to \; (\neg A \to B$)
2) $A \vee B \; \to \; A \to B$
3) $A \vee B \; \to \; \neg(\neg A \& B)$
4) $A \vee B \; \to \; B \vee A$
5) $A \vee B \; \to \; \neg A \vee \neg B$
6) $A \vee B \; \to \; \neg(\neg A \& \neg B)$
Разбор 1). По теореме о дедукции предложенная импликация эквивалентна тому, что из $A \vee B$ и $A$ вытекает $B$. Проверим это. $(A \vee B) \& \neg A = B \& \neg A \Rightarrow B$.
Разбор 2). Проверим, всегда ли из $A \vee B$ и $A$ следует $B$. По правилу поглощения $(A \vee B) \& A = A$. Если $A = 1$, $B = 0$, то из левой части не следует правая. Значит, 2) – не тавтология.
Разбор 3). Преобразуем правую часть: $\neg(\neg A \& B) = \neg B \vee A = B \to A$. Тогда 3) эквивалентно $A \vee B \; \to \; (B \to A)$. Но, как можно видеть из таблицы истинности, из “A или B” не следует $B \to A$: достаточно взять $B = 1$, $A = 0$. Следовательно, 3) – не тавтология. Можно применить метод резолюций и показать, что конъюнкция левой части импликации и отрицания ее правой части не будет тождественно ложной. В данном случае $(A \vee B) \& \neg A \& B = B\&\neg A\not\equiv 0$.
Использование математической логики для решения практических задач
Язык математической логики универсален, потому что процедура формализации позволяет выделить форму высказываний и уже для формальных логических выражений провести процедуру логического вывода, не отвлекаясь на конкретное содержание. Язык математической логики находит применение как при описании информационных систем, так и при анализе алгоритмов. Кроме того, этот язык используется в моделях представления знаний [Волкова, с. 60].
Вывод новых знаний в рамках логической модели представления знаний заключается в получении некоторого утверждения из имеющихся аксиом и правил вывода. Если в результате вывода утверждение получено, то оно считается истинным и является логическим следствием из аксиом.
В этом случае задачей пользователя или программиста является описание предметной области совокупностью утверждений в виде логических формул. Доказательство истинности утверждения осуществляется ЭВМ на основе исходных утверждений. Для логического вывода можно использовать метод резолюций.
В качестве простого примера формализации утверждений запишем следующее предложение на языке логики предикатов: “если некоторые здунцы не едят быстро, то все бутявки не зюмят”.
Определим предикаты $P(x)$ = “$x$ ест быстро”, $Q(x)$ = “$x$ зюмит”. Утверждается, что $\exists x\, \neg P(x) \; \to \; \forall y \, \neg Q(y)$.
Литература
Степанова – Математическая логика. Конспект лекций (2002)
Гринченков, Потоцкий – Математическая логика и теория алгоритмов для программистов (2010)
Основы логики
Понятие имеет две основные логические характеристики: содержание и объем.
Содержанием понятия называется совокупность существенных признаков, отраженных в этом понятии.
Объем понятия — это множество предметов, каждому из которых принадлежат признаки, относящиеся к содержанию понятия.
Совместимые и несовместимые понятия
По объему понятия могут быть совместимыми или несовместимыми. Объемы совместимых понятий совпадают полностью или частично (т.е. существуют объекты, имеющие признаки обоих понятий). Объемы несовместимых понятий не включают ни одного общего элемента.
Отношения совместимых понятий:
l пересечение (часть элементов объема каждого понятия входит в объем другого понятия); например, «мальчик»–«болельщик»;
l тождество (полное совпадение объемов понятий);
l подчинение (объем одного понятия полностью входит в объем другого); например, «акула»–«рыба».
Отношения несовместимых понятий:
l соподчинение; например, «рыба»–«птица» (соподчинены понятию «животное»);
l противоположность (объект, не попадающий под одно понятие, может не попадать и под другое); например, «черный»–«белый»;
l противоречие (объект принадлеит объему либо одного, либо другого понятия); например, «светящийся объект»–«несветящийся объект».
Высказывание
Высказывание (суждение) — форма мышления, в которой что-либо утверждается или отрицается о предметах, их свойствах, или отношениях.
Высказывание характеризуется своим содержанием и формой.
Умозаключение
Умозаключение — форма мышления, посредством которой из одного или нескольких высказываний, называемых посылками, мы по определенным правилам вывода получаем заключение.
С точки зрения содержания мышление может давать истинное или ложное отражение мира, формально же оно может быть логически правильным или неправильным.
Логические операции
Высказывание, включающее другие высказывания, называют сложным. Для образования сложных высказываний используют логические операции (связки). Рассмотрим некоторые из них (в порядке приоритета при вычислении логических выражений).
Инверсия (отрицание)
Инверсия — это логическая операция, образующая сложное высказывание, истинное тогда и только тогда, когда исходное высказывание ложно.
В выражениях обозначается ¬A или Ā.
Читается «НЕ» (например, «не А»).
Конъюнкция (логическое умножение)
Конъюнкция — это логическая операция, образующая сложное высказывание, истинное тогда и только тогда, когда истинны оба исходных высказывания.
В выражениях обозначается AÙ B или A&B (знак может не указываться — AB).
Читается «И» (например, «А и Б»)
Дизъюнкция (логическое сложение)
Дизъюнкция — это логическая операция, образующая сложное высказывание, истинное тогда, когда истинно хотя бы одно из исходных высказываний.
В выражениях обозначается AÚ B, иногда A+B.
Читается «ИЛИ» (например, «А или Б»)
Импликация (следование)
Импликация — это логическая операция, образующая сложное высказывание, ложное тогда и только тогда, когда первое исходное высказывание истинно, а второе — ложно.
В выражениях обозначается A Þ B или A ® B.
Читается «ЕСЛИ. ТО» (например, «если А, то Б»)
Эквивалентность (равнозначность)
Эквивалентность — это логическая операция, образующая сложное высказывание, истинное тогда и только тогда, когда значения исходных высказываний совпадают.
В выражениях обозначается A Û B или A º B.
Читается «ТОГДА И ТОЛЬКО ТОГДА, КОГДА» (например, «А тогда и только тогда, когда Б»)
Таблицы истинности логических операций
Таблица истинности — таблица, в которой указаны значения логической функции для всех возможных комбинаций значений ее аргументов.
Число комбинаций (строк таблицы) определяется как 2 N , где N — количество аргументов (т. е. при двух аргументах число строк — 4, при 3 — 8 и так далее).