Сегодня мы научимся записывать логическую формулу по таблице истинности.
Правило 1. По каждому набору двоичных переменных, на которых функция принимает значение единицы записать элементарную конъюнкцию n ранга (логическое произведение всех двоичных переменных, при этом инвертируются те переменные, которые имеют значение нуля) и полученные конъюнкции объединить знаком дизъюнкции. Такая форма функции называется ДНФ (совершенная дизъюнктивно — нормальная форма).
Правило 2. По каждому набору двоичных переменных, на которых функция принимает значение нуля записать элементарную дизъюнкцию всех n переменных (логическая сумма всех двоичных переменных, при этом инвертируются те переменные, которые имеют значение единицы) и полученные дизъюнкции объединить знаком конъюнкции. Такая форма функции называется КНФ (совершенная конъюнктивно — нормальная форма).
|
ДНФ (правило 1) |
Таблица истинности |
КНФ (правило 2) |
|||||||||||||||
|
|||||||||||||||||
Слева и справа от таблицы истинности — две формы одной и той же логической функции. Она была задана своей таблицей истинности, в которой перечислены все возможные значения логических переменных и те значения, которые принимает функция на каждом из них.
Рассмотрим более сложный пример. Во — первых, рассматриваемая функция имеет три аргумента (логических переменных) F(A, B, C), во — вторых, условие задачи задано не просто таблицей истинности, а сформулировано следующим образом: «Заданная функция трех переменных принимает значение единицы на наборах 2, 3, 6».
Что это означает? Если функция имеет три аргумента, то возможных значений будет 8! Нарисуем сами таблицу истинности по заданному условию. В ней будет 9 строк, 8 — для значений аргументов и одна строка для заголовков. Заполняем первый столбец — четыре 0, четыре 1. Второй столбец — два нуля, две единицы, опять два нуля и две единицы. Третий столбец — 0, 1, 0, 1, 0, 1, 0, 1. Если внимательно посмотреть, то увидим в нашей таблице двоичное представление цифр 0, 1, 2, 3, 4, 5, 6, 7. А теперь заполняем четвертый столбец, ведь по условию функция принимает значение единицы там, где записаны цифры 2, 3 и 6. А это комбинация 0 1 0 (2), 0 1 1 (3) и 1 1 0 (6). поэтому ставим единицы в соответствующих строках, а в остальных запишем нули.
|
A |
B |
C |
F(A, B, C) |
|
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
0 |
|
0 |
1 |
0 |
1 |
|
0 |
1 |
1 |
1 |
|
1 |
0 |
0 |
0 |
|
1 |
0 |
1 |
0 |
|
1 |
1 |
0 |
1 |
|
1 |
1 |
1 |
0 |
Часто условие бывает задано уже нарисованной таблицей истинности. Тогда сразу по ней можно записать либо ДНФ логической функции, либо КНФ. Так как в нашем случае в значениях функции меньше единиц, то запишем дизъюнктивную форму логической функции по правилу 1.
и согласно законам алгебры логики произведем преобразования:
Подсказка: сумма переменной С и ее отрицания равна 1, далее в выражении используем второй дистрибутивный закон, затем в одной из скобок имеем опять сумму переменной А и ее отрицания, что дает 1.
|
Построим таблицу истинности полученного логического выражения для того, чтобы убедиться в правильности проведенных преобразований. Видим, что последний столбец таблицы совпадает с последним столбцом исходной таблицы истинности. Тем самым мы доказали правильность проведенных преобразований! |
|
Таблица истинности — это таблица, устанавливающая соответствие между всеми возможными наборами логических переменных, входящих в логическую функцию и значениями функции.
Таблицы истинности применяются для:
— вычисления истинности сложных высказываний;
— установления эквивалентности высказываний;
— определения тавтологий.
1. Установление истинности сложных высказываний.
Пример 1. Установить истинность высказывания · С
Решение. В состав сложного высказывания входят 3 простых высказывания: А, В, С. В таблице заполняются колонки значениями (0, 1). Указываются все возможные ситуации. Простые высказывания от сложных отделяются двойной вертикальной чертой.
При составлении таблицы надо следить за тем, чтобы не перепутать порядок действий; заполняя столбцы, следует двигаться “изнутри наружу”, т.е. от элементарных формул к более и более сложным; столбец, заполняемый последним, содержит значения исходной формулы.
|
А |
В |
С |
А+ |
· С |
||
|
0 |
0 |
0 |
1 |
1 |
0 |
0 |
|
0 |
0 |
1 |
1 |
1 |
0 |
0 |
|
0 |
1 |
0 |
0 |
0 |
1 |
0 |
|
0 |
1 |
1 |
0 |
0 |
1 |
1 |
|
1 |
0 |
0 |
1 |
1 |
0 |
0 |
|
1 |
0 |
1 |
1 |
1 |
0 |
0 |
|
1 |
1 |
0 |
0 |
1 |
0 |
0 |
|
1 |
1 |
1 |
0 |
1 |
0 |
0 |
Из таблицы видно, что данное высказывание истинно только в случае, когда А=0, В=1, С=1. Во всех остальных случаях оно ложно.
2. Эквивалентность высказываний.
С помощью таблиц истинности можно установить эквивалентность двух или нескольких высказываний.
Высказывания называются эквивалентными, если соответствующие значения каждого из них совпадают в таблице истинности.
Пример 2. Утверждается, что высказывание А+В· С эквивалентно высказыванию (А+В)· (А+С)
Решение. Проверка ведется путем составления таблицы истинности.
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
А |
В |
С |
В С |
А+В· С |
А+В |
А+С |
(А+В)· (А+С) |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
|
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
|
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
|
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
|
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Сравнивая 5-ю и 8-ю колонки убеждаемся, что все значения, получаемые по формуле А+В· С, совпадают со значениями, получаемыми по формуле (А+В)· (А+С), т.е. высказывания эквивалентны (равносильны). Одно может заменить другое.
Эквивалентные (равносильные) высказывания соединяют знаком º А + В·Сº (А+В)· (А+С).
Отметим различие между эквивалентностью и эквиваленцией.
Эквиваленция является логической операцией, позволяющей по двум заданным высказываниям А и В построить новое А« В.
Эквивалентность же является отношением между двумя составными высказываниями, состоящим в том, что их значения истинности всегда одни и те же.
3. Тавтология.
Пусть дано высказывание А· и необходимо составить таблицу истинности.
Высказывание А· ложно, истинность его не зависит от истинности высказывания А.
|
А |
А· |
|
|
1 |
0 |
0 |
|
0 |
1 |
0 |
Рассмотрим высказывание В+.
В этом случае высказывание В+ всегда истинно, независимо от истинности В.
|
В |
В+ |
|
|
1 |
0 |
1 |
|
0 |
1 |
1 |
Высказывания, истинность которых постоянна и не зависит от истинности входящих в них простых высказываний, а определяется только их структурой, называются тождественными или тавтологиями.Различают тождественно-истинные и тождественно-ложные высказывания.
В формулах каждое тождественно-истинное высказывание заменяется 1, а тождественно-ложное — 0.
Закон исключенного третьего.
A· º 0
В+º 1
Пример 3. Докажите тавтологию (XÙ Y)® (XÚ Y)
Решение.
|
X |
Y |
XÙ Y |
XÚ Y |
(XÙ Y)® (XÚ Y) |
|
0 |
0 |
0 |
0 |
1 |
|
0 |
1 |
0 |
1 |
1 |
|
1 |
0 |
0 |
1 |
1 |
|
1 |
1 |
1 |
1 |
1 |
Т.к. высказывание (XÙ Y)® (XÚ Y) всегда истинно, то оно является тавтологией.
Пример 4. Докажите тавтологию ((X® Y)Ù (Y® Z))® (X® Z)
Решение.
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ F1 _ _ _ _ F2 _ _ _ _ _ F
|
X |
Y |
Z |
X® Y |
Y® Z |
X® Z |
F1Ù F2 |
(F1Ù F2) ® F3 |
|
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
|
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
|
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
|
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
|
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
|
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Из таблицы видно, что исследуемое высказывание — тавтология, т.к. оно истинно постоянно.
Логические выражения
Каждое составное высказывание можно выразить в виде формулы (логического выражения), в которую войдут логические переменные, обозначающие высказывания, и знаки логических операций, обозначающие логические функции. Для записи составных высказываний в виде логических выражений на формальном языке (языке алгебры логики) в составном высказывании нужно выделить простые высказывания и логические связи между ними. Истинность или ложность составных высказываний можно определять чисто формально, руководствуясь законами алгебры высказываний, не обращаясь к смысловому содержанию высказываний.
Приоритет логических операций: 1) инверсия, 2) конъюнкция, 3) дизъюнкция.
Например, А= «2х2=5» =0
В= «2х2=4» =1
F=(AvB)&( ¬Av¬B)=(0v1)&(1v0)=1&1=1
ТАБЛИЦЫ ИСТИННОСТИ Для каждого составного высказывания (логического выражения) можно построить таблицу истинности, которая определяет его истинность или ложность при всех возможных комбинациях исходных значений простых высказываний (логических переменных).
При этом целесообразно руководствоваться
- определить количество строк в ТИ, которое равно количеству возможных комбинаций значений логических переменных, входящих в логическое выражение: кол-во строк = 2n, где n — количество логических переменных. В нашем случае кол-во строк = 22 = 4;
- определить количество столбцов в ТИ, равное количеству логических переменных плюс количество логических операций. Кол-во столбцов = 2 + 5 = 7;
- построить ТИ с указанным количеством строк и столбцов, обозначить столбцы и внести возможные наборы значений исходных логических переменных
A B AvB ¬A ¬B ¬Av¬B (AvB)&( ¬Av¬B)
0 0 0 1 1 1 0
0 1 1 1 0 1 1
1 0 1 0 1 1 1
1 1 1 0 0 0 0
4. заполнить ТИ по столбцам, выполняя базовые логические операции в необходимой последовательности и в соответствии с их ТИ. Теперь мы можем определить значение логической функции для любого набора значений логических переменных.
РАВНОСИЛЬНЫЕ ЛОГИЧЕСКИЕ ВЫРАЖЕНИЯ. Логические выражения, у которых ТИ совпадают, называются равносильными (эквивалентными). Обозначение — знак «=».
Например, доказать, что ¬A&¬B=¬(AvB).
A B ¬A ¬B ¬A& ¬B
0 0 1 1 1
0 1 1 0 0
1 0 0 1 0
1 1 0 0 0
A B AvB ¬(AvB)
0 0 0 1
0 1 1 0
1 0 1 0
1 1 1 0
Таблицы истинности совпадают, следовательно, логические выражения равносиьны: ¬A&¬B=¬(AvB)
Импликация и эквиваленция
В обыденной и научной речи кроме базовых логических связок «и», «или», «не», используются и некоторые другие: «если… то…», «тогда… и только тогда, когда…» и др. Некоторые из них имеют свое название и свой символ и им соответствуют определенные логические функции.
Логическое следование (импликация) образуется соединением двух высказываний в одно с помощью оборота речи «если…, то..,».
Логическая операция импликации «если А то В», обозначается А ® B и выражается с помощью логической функции F14. которая задается соответствующей таблицей истинности.
Таблица истинности логической функции импликация
|
A |
B |
А ®B |
|
0 |
0 |
1 |
|
0 |
1 |
1 |
|
1 |
0 |
0 |
|
1 |
1 |
1 |
Составное высказывание, образованное с помощью операции логического следования (импликации), ложно тогда и только тогда, когда из истинной предпосылки (первого высказывания) следует ложный вывод (второе высказывание).
Например, высказывание «Если число делится на 10, то оно делится на 5» истинно, т.к. истинны и первое высказывание (предпосылка), и второе высказывание (вывод).
Высказывание «Если число делится на 10, то оно делится на З» ложно, т.к. из истинной предпосылки делается ложный вывод.
Однако операция логического следования несколько отличается от обычного понимания слова «следует». Если первое высказывание (предпосылка) ложно, то вне зависимости от истинности или ложности второго высказывания (вывода) составное высказывание истинно.
Это можно понимать таким образом, что из неверной предпосылки может следовать что угодно.
В алгебре высказываний все логические функции могут быть сведены путем логических преобразований к трем базовым: логическому умножению, логическому сложения и логическому отрицанию.
Докажем методом сравнения таблиц истинности, что операция импликации А ® B равносильна логическому выражению ¬AvB.
Таблица истинности логического выражения ¬AvB
|
A |
B |
¬A |
¬AvB |
|
0 |
0 |
1 |
1 |
|
0 |
1 |
1 |
1 |
|
1 |
0 |
0 |
0 |
|
1 |
1 |
0 |
1 |
Таблицы истинности совпадают, что и требовалось доказать.
Логическое равенство (эквивалентность) образуется соединением двух высказываний в одно с помощью оборота речи «… тогда и только тогда, когда…».
Логическая операция эквивалентности «А эквивалентно В» обозначается А~В и выражается с помощью логической функции , которая задается соответствующей таблицей истинности.
Таблица истинности логической функции эквивалентности
|
А |
В |
А~В |
|
0 |
0 |
1 |
|
0 |
1 |
0 |
|
1 |
0 |
0 |
|
1 |
1 |
1 |
Составное высказывание, образованное с помощью логической операции эквивалентности истинно тогда и только тогда, когда оба высказывания одновременно либо ложны, либо истинны.
Рассмотрим, например, два высказывания А = «Компьютер может производить вычисления» и В = «Компьютер включен». Составное высказывание, полученное с помощью операции эквивалентности истинно, когда оба высказывания либо истинны, либо ложны:
«Компьютер может производить вычисления тогда и только тогда, когда компьютер включен».
«Компьютер не может производить вычисления тогда и только тогда, когда компьютер не включен».
Составное высказывание, полученное с помощью операции эквивалентности ложно, когда одно высказывание истинно, а другое — ложно:
«Компьютер может производить вычисления тогда и только тогда, когда компьютер не включен».
«Компьютер не может производить вычисления тогда и только тогда, когда компьютер включен».