Алгебра логики
Функции тождественны, если $f(x_1, x_2, \dots, x_n)=g(x_1, x_2, \dots, x_n)$ на всех наборах аргументов (таблицы истинности совпадают).
$f(\overline
Важно: Если в булевом тождестве заменить каждую функцию на двойственную ей, снова получится верное тождество. В приведённых выше формулах легко найти двойственные друг другу пары.
Нормальные и совершенные нормальные формы: КНФ, ДНФ, СДНФ, СКНФ
Простая конъюнкция или конъюнкт = конъюнкция некоторого конечного набора переменных или их отрицаний, причём каждая переменная встречается не более одного раза.
Дизъюнктивная нормальная форма (ДНФ) = дизъюнкция простых конъюнкций. Пример: $a \overline c\lor b c\lor\overline$.
Совершенная ДНФ (СДНФ) относительно некоторого набора переменных = ДНФ, у которой в каждую конъюнкцию входят все переменные данного набора, причём в одном и том же порядке. Пример: $a \overline c\lor a b c\lor\overline b\overline
СДНФ и СКНФ можно построить по таблице истинности.
Булева Алгебра (Алгебра Буля)
Формально: непустое множество $A$ с двумя бинарными операциями $\land$ (конъюнкция), $\lor$ (дизъюнкция), унарной операцией $\lnot$ (отрицание) и двумя выделенными элементами: 0 (или Ложь) и 1 (или Истина) такими, что для всех »a», »b» и »c» из множества $A$ верны следующие аксиомы:
Проблема разрешимости
Все формулы алгебры логики делятся на тождественно истинные (всегда 1), тождественно ложные (всегда 0) и выполнимые (иногда 0, иногда 1).
Проблема разрешимости: к какому классу (из вышеперечисленных) относится данная формула?
Для каждой формулы может быть составлена таблица истинности, которая и даст ответ на поставленный вопрос, но при большом количестве переменных практическое использование таблиц истинности затруднительно.
Нетабличный способ определения формулы к данному классу
Способ состоит в приведении формулы к нормальной форме (ДНФ или КНФ) и использовании правил, которые позволяют определить, какой является формула (тождественно истинной, тождественно ложной, выполнимой).
- Критерии тождественной истинности: необходимо и достаточно, чтобы любая дизъюнкция, входящая в КНФ, содержала переменную и её отрицание.
- Критерии тождественной ложности: необходимо и достаточно, чтобы любая конъюнкция, входящая в ДНФ, содержала переменную и её отрицание.
Замкнутые классы. Монотонные функции
Замкнутый класс — такое множество булевых функций, замыкание которого относительно операции суперпозиции совпадает с ним самим: $[P]=P$. Другими словами, любая функция, которую можно выразить формулой с использованием функций множества $P$, снова входит в это же множество.
В 1941 году Эмиль Пост представил полное описание системы замкнутых классов (решетку Поста).
Примеры замкнутых классов:
Множество $P_2$ всех возможных булевых функций замкнуто.
Особо важны для теории булевых функций следующие замкнутые классы, называемые предполными классами:
- Класс $T_0$ функций, сохраняющих 0: $T_0=\left\
- Класс $T_1$ сохраняющих 1: $T_1=\left\
- $S$ самодвойственных функций: $S=\left\
)=\overline - $M$ монотонных функций: $M=\left\
- $L$ линейных функций: $L=\left\
Ни один из предполных классов не содержится целиком в объединении четырёх остальных; любой замкнутый класс булевых функций, отличный от $P_2$, целиком содержится хотя бы в одном из пяти предполных классов.
Другими важными замкнутыми классами являются:
- Класс конъюнкций K, являющийся замыканием множества $\<\land,0,1\>$. Он представляет собой множество функций вида $c_0\land(c_1\lor x_1)\land\ldots\land(c_n\lor x_n)$.
- Класс дизъюнкций D, являющийся замыканием множества $\<\lor,0,1\>$. Он представляет собой множество функций вида $c_0\lor(c_1\land x_1)\lor\ldots\lor(c_n\land x_n)$.
- Класс функций одной переменной U, содержащий только константы, отрицание и селектор (функцию, равную одному из своих аргументов на всех наборах их значений).
- Класс $O^m$ функций (m — любое натуральное, большее единицы число), удовлетворяющих следующему условию: для любых m наборов, на которых функция принимает нулевое значение, найдется переменная, также принимающая нулевое значение на всех этих наборах.
- Класс $O^\infty$ функций, для которых выполнено условие $f(x_1,\ldots,x_n)\ge x_i$, где $x_i$ — одна из переменных функции.
- Класс $I^m$ функций (m — любое натуральное, большее единицы число), удовлетворяющих следующему условию: для любых m наборов, на которых функция принимает единичное значение, найдется переменная, также принимающая единичное значение на всех этих наборах.
- Класс $I^\infty$ функций, для которых выполнено условие $f(x_1,\ldots,x_n)\le x_i$, где $x_i$ — одна из переменных функции.
В 1941 году Эмиль Пост показал, что любой замкнутый класс булевых функций является пересечением конечного числа описанных выше классов, приведя полное описание структуры замкнутых классов двузначной логики. Также Пост установил, что любой замкнутый класс может быть порожден конечным базисом.
Полные системы функций. Базисы + Пост — основная теорема о функциональной полноте
Множество функций $A$ — полная система, если замыкание $A$ совпадает с множеством всех булевых функций $[A]=P_2$ (т.е. любую логическую функцию можно выразить формулой с использованием только функций множества $A$).
Критерий Поста формулирует необходимое и достаточное условие полноты системы булевых функций:
Система булевых функций полна тогда и только тогда, когда она не содержится целиком ни в одном из классов $T_0$, $T_1$, $S$, $M$, $L$. В частности, если функция не входит ни в один из классов Поста, она сама по себе формирует полную систему. В качестве примера можно назвать штрих Шеффера (отрицание конъюнкции).
Широко известны такие полные системы булевых функций:
- $\left\<\land,\lor,\neg\right\>$ (конъюнкция, дизъюнкция, отрицание) — ДНФ.
- $\left\<\land,\oplus,1\right\>$ (конъюнкция, сложение по модулю 2, константа 1) — полином Жегалкина.
Полная система функций называется базисом, если она перестаёт быть полной при исключении из неё любого элемента. Первая из упоминавшихся выше полных систем базисом не является, поскольку согласно законам де Моргана либо дизъюнкцию, либо конъюнкцию можно исключить из системы и восстановить с помощью остальных двух функций. Вторая система является базисом — все три её элемента необходимы для полноты.
Максимально возможное число булевых функций в базисе — 4.
Иногда говорят о системе функций, полной в некотором замкнутом классе, и соответственно о базисе этого класса. Например, систему $\left\<\oplus,1\right\>$ можно назвать базисом класса линейных функций.
Алгебра Жегалкина
Полином Жегалкина — полином над $Z_2$ (коэффициенты только 0 и 1), в качестве произведения — конъюнкция, а в качестве сложения — исключающее или (xor, не равно, сложение по модулю 2). Общий вид:
$P = a \oplus \bigoplus_< \begin
По теореме Жегалкина каждая булева функция единственным образом представляется в виде полинома Жегалкина.
Переключательные схемы
Функции проводимости $F$ некоторых переключательных схем:
a)
Схема не содержит переключателей и проводит ток всегда, следовательно $F=1$;
б) Схема содержит один постоянно разомкнутый контакт, следовательно $F=0$;
в) Схема проводит ток, когда переключатель х замкнут, и не проводит, когда х разомкнут, следовательно, $F(x) = x$;
г) — Схема проводит ток, когда переключатель х разомкнут, и не проводит, когда $х$ замкнут, следовательно, $F(x) = \bar x$;
д) Схема проводит ток, когда оба переключателя замкнуты, следовательно, $F(x) = x \land y$;
е) Схема проводит ток, когда хотя бы один из переключателей замкнут, следовательно, $F(x)=x \lor y$;
ж) Схема состоит из двух параллельных ветвей и описывается функцией .
Две схемы называются равносильными, если через одну из них проходит ток тогда и только тогда, когда он проходит через другую (при одном и том же входном сигнале).
Из двух равносильных схем более простой считается та схема, функция проводимости которой содержит меньшее число логических операций или переключателей.
Способы доказательства тавтологии и следствия
Тавтологией называется тождественно истинное высказывание, верное при любых значениях своих компонентов. Формула в исчислении высказываний является тавтологией или тождественно истинной, если её значение для любых значений аргументов истинно.
Примеры тавтологий:
- $ A \to A $ («Из »A» следует »A»»)
- $(A) \lor (\lnot A)$ («»A» или не-»A»»)
- $\overline
$.
- $(P \land (P \to Q)) \to Q$
- $A \to (B \to A)$
Формула F называется тавтологией, или тождественно истинной формулой, если F истинно при любой интерпретации.
Понятие тавтологии "двойственно"’ понятию выполнимой формулы: $F$ – тавтология тогда и только тогда, когда $\lnot F$ не выполнима. Определение эквивалентных формул, данное выше, может быть переформулировано следующим образом: F эквивалентна G, если F є G – тавтология.
Формула является »тождественно истинной», если она истинна при любых значениях входящих в неё переменных. Вот несколько широко известных примеров тождественно истинных формул логики высказываний:
Законы де Моргана:
1) $ \neg (p \lor q) \leftrightarrow (\neg p \land \neg q)$;
2) $ \neg (p \land q) \leftrightarrow (\neg p \lor \neg q)$;
Закон контрапозиции:
$(p\to q)\leftrightarrow(\neg q\to \neg p)$;
1) $p\lor(p\land q)\leftrightarrow p$;
2) $p\land(p\lor q)\leftrightarrow p$;
1) $p\land(q\lor r)\leftrightarrow(p\land q)\lor(p \land r)$;
2) $p\lor(q\land r)\leftrightarrow(p\lor q)\land(p \lor r)$.
Общие свойства символа тавтология
Правило введения и удаления логических знаков
Метод Резолюции. Теорема о замене. Теорема о резолюциях. Доказательство тавтологии с помощью метода резолюции
Правило резолюций – это правило вывода, восходящее к методу доказательства теорем через поиск противоречий; используется в логике высказываний и логике предикатов первого порядка. Правило резолюций, применяемое последовательно для списка резольвент, позволяет ответить на вопрос, существует ли в исходном множестве логических выражений противоречие
Пусть $C_1$ и $C_2$ — два предложения в исчислении высказываний, и пусть $C_1 = P \lor C’_1$, а $C_2 = \lnot P \lor C’_2$, где $P$ — пропозициональная переменная, а $C’_1$ и $C’_2$ — любые предложения (в частности, может быть, пустые или состоящие только из одного литерала). Правило вывода
называется правилом резолюции. Предложения C1 и C2 называются »резольвируемыми» (или »родительскими»), предложение $C’_1 \lor C’_2$ — »резольвентой», а формулы $P$ и $\lnot P$ — »контрарными» литералами.
Алгоритм:
- Составляем список дизъюнктов.
- Находим среди них какую-либо пару, в которой один дизъюнкт содержит переменную, а другой — ее отрицание. На основе этих двух дизънктов получаем один новый, которы заносим в список. И начинаем поиск подходящей пары снова.
- Все это продолжается до тех пор, пока на некотором шаге в списке не окажется пара $a$ и $\lnot a$.
Исчисление высказываний
Составное высказывание
Сокращенные таблицы истинности
Выбираем значение переменной, подставляем в логическое выражение, упрощаем выражение, заполняем строки в таблице истинности. Повторяем этот шаг пока таблица истинности не будет заполнена.
Формальные теории (исчисление)
Формальная теория — результат строгой формализации теории, предполагающей полную абстракцию от смысла слов используемого языка, причем все условия, регулирующие употребление этих слов в теории, явно высказаны посредством аксиом и правил, позволяющих вывести одну фразу из других.
Формальная теория – это совокупность абстрактных объектов, не связанных с реальным миром, в котором представлены правила оперирования множеством символов в строго синтаксической трактовке без учета их смыслового содержания, т.е. семантики.
Формальная теория считается определенной, если:
- Задано конечное или счётное множество произвольных символов. Конечные последовательности символов называются выражениями теории.
- Имеется подмножество выражений, называемых формулами.
- Выделено подмножество формул, называемых аксиомами.
- Имеется конечное множество отношений между формулами, называемых правилами вывода.
Аксиоматичное построение исчисления высказываний, правило вывода (правило заключения)
- алфавит есть множество символов:
- $а, b, . а_1, b_1. $ — (пропозициональные) переменные, значением которой может быть логическое высказывание;
- $\neg, \land, \lor, \to$ (отрицание, конъюнкция, дизъюнкция и импликация) — пропозициональные связк;
- (,) — скобки, служебные символы;
- Если $P$ — пропозициональная переменная, то $P$ — формула.
- Если $A$ — формула, то $\neg A$ — формула.
- Если $A$ и $B$ — формулы, то $A \to B$, $A \land B$ и $A \lor B$ — формулы.
- Других соглашений нет.
- $A \to (B \to A)$;
- $((A \to (B \to C)) \to ((A \to B) \to (A \to C)))$;
- $A \land B \to A$;
- $A \land B \to B$;
- $A \to (B \to (A \land B))$;
- $A \to (A \lor B)$;
- $B \to (A \lor B)$;
- $(A \to C) \to ((B \to C) \to ((A \lor B) \to C))$;
- $\neg A \to (A \to B)$;
- $(A \to B) \to ((A \to \neg B)\to \neg A)$;
- $A\lor\neg A$.
вместе с единственным правилом вывода:
Сравнение результатов аксиоматической теории исчисления с результатами, относящимися к тавтологии
Предикаты. n-местный предикат. Кванторы
Предикат (»n»-местный, или »n»-арный) — функция с множеством значений $\< 0,1 \>$ (или «ложь» и «истина»), определённая на множестве $M=<
_<1>>\times < _<2>>\times \ldots \times < _ >$. Таким образом, каждый набор элементов множества »M» он характеризует либо как «истинный», либо как «ложный». Тождественно-истинный предикат: $P\left ( x_1, . x_n \right) \equiv 1$ (на любом наборе аргументов равен 1).
Тождественно-ложный предикат: $P\left ( x_1, . x_n \right) \equiv 0$ (на любом наборе аргументов равен 0).
Предикат выполнимый, если хотя бы на одном наборе аргументов он равен 1.
Квантор — общее название для логических операций, ограничивающих область истинности какого-либо предиката. Чаще всего используются:
- Квантор всеобщности $\forall$ — «для всех…», «для каждого…» или «каждый…», «любой…», «для любого…»).
- Квантор существования $\exists$, читается: «существует…» или «найдётся…».
В математической логике приписывание квантора к формуле называется связыванием или навешиванием квантора.
Связанные переменные
Переменная $v$ связана в формуле $F$, если $F$ содержит $Kv$, где $K$ — квантор.
Предикаты на конечных областях. Логика одноместных предикатов
Значений $x$ конечное число, их можно перебрать.
Конъюнкция — пересечение областей определения, дизъюнкция — объединение областей определения, отрицание — дополнение области определения.
Кванторы по предикатным переменным
Правило отрицания кванторов: применяется для построения отрицаний высказываний, содержащих кванторы, и имеет вид:
Алгебра логики
Высказывание — повествовательное предложение, о котором однозначно можно сказать истинно оно или ложно.
Конъюнкцией высказываний А и В называется высказывание, читаемое: «А и В», которое истинно в единственном случае, когда высказывания А и В истинны одновременно.
Дизъюнкцией высказываний А и В называется высказывание, читаемое: «А или В», которое ложно в единственном случае, когда оба высказывания ложны одновременно.
Импликацией высказываний А и В называется высказывание, читаемое: «Если А, то В», которое ложно в единственном случае, когда высказывание А истинно и высказывание В ложно.
Эквиваленцией высказываний А и В называется высказывание, читаемое: «А тогда и только тогда, когда В», которое истинно в двух случаях, когда высказывания А и В истинны одновременно, когда высказывания А и В ложны одновременно.
Отрицанием высказывания А называется высказывание, читаемое «не А», которое ложно, когда А истинно и истинно, когда высказывание А ложно.
Обозначение операций над высказываниями.
Обозначение, запись, чтение высказываний. Логическое значение высказывания.
Если известно по условию задачи, какое именно повествовательное предложение названо или обозначено символом А, то А – логическая константа.
Например: А : «Декабрь – зимний месяц». А – логическая константа.
Если неизвестно какое повествовательное предложение обозначено этим символом, то А – логическая переменная. Из логических переменных, символов бинарных и унарных операций, скобок составляются выражения с логическими переменными. Каждая логическая переменная является элементарным выражением с логической переменной. Если в записи выражения имеется хотя бы один символ операции, то оно называется составным.
Два выражения с логическими переменными называются равносильными, если при каждом наборе логических значений переменных в них входящих, эти выражения принимают одно и то же значение.
Если при каждом наборе логических значений переменных, входящих в данное выражение, оно принимает ложное значение, то данное выражение называется тождественно-ложным или противоречием. Тождественно – ложное выражение F обозначают: F≡0.
Если при каждом наборе логических значений переменных, входящих в данное выражение, оно принимает истинное значение, то данное выражение называется тождественно-истинным или тавтологией. Тождественно – истинное выражение F обозначают: F≡1.
Не всякое выражение является тождественно–истинным или тождественно-ложным. Если существуют наборы, при которых выражение принимает истинное значение, и существуют наборы, при которых оно принимает ложное значение, то выражение не является ни тождественно-истинным, и ни тождественно-ложным.
Свойства операций над высказываниями.
Каждое свойство операций над высказываниями является равносильностью двух выражений с логическими переменными. Будем называть основные свойства основными равносильностями.
Каждая сформулированная равносильность доказывается с помощью таблицы истинности.
Формулы и законы логики
На вводном уроке, посвящённом основам математической логики, мы познакомились с базовыми понятиями этого раздела математики, и сейчас тема получает закономерное продолжение. Помимо нового теоретического, а точнее даже не теоретического – а общеобразовательного материала нас ожидают практические задания, и поэтому если вы зашли на данную страницу с поисковика и/или плохо ориентируетесь в материале, то, пожалуйста, пройдите по вышеуказанной ссылке и начните с предыдущей статьи. Кроме того, для практики нам потребуется 5 таблиц истинности логических операций, которые я настоятельно рекомендую переписать от руки.
НЕ запомнить, НЕ распечатать, а именно ещё раз осмыслить и собственноручно переписать на бумагу – чтобы они были перед глазами:
– таблица НЕ;
– таблица И;
– таблица ИЛИ;
– импликационная таблица;
– таблица эквиваленции.Это очень важно. В принципе, их было бы удобно занумеровать «Таблица 1», «Таблица 2» и т.д., но я неоднократно подчёркивал изъян такого подхода – как говорится, в одном источнике таблица окажется первой, а в другом – сто первой. Поэтому будем использовать «натуральные» названия. Продолжаем:
На самом деле с понятием логической формулы вы уже знакомы. Приведу стандартное, но довольно-таки остроумное определение: формулами алгебры высказываний называются:
1) любые элементарные (простые) высказывания ;
2) если и – формулы, то формулами также являются выражения вида
.Никаких других формул нет.
В частности формулой является любая логическая операция, например логическое умножение . Обратите внимание на второй пункт – он позволяет рекурсивным образом «создать» сколь угодно длинную формулу. Поскольку – формулы, то – тоже формула; так как и – формулы, то – тоже формула и т.д. Любое элементарное высказывание (опять же согласно определению) может входить в формулу неоднократно.
Формулой не является, например, запись – и здесь прослеживается очевидная аналогия с «алгебраическим мусором» , из которого не понятно – нужно ли числа складывать или умножать.
Логическую формулу можно рассматривать, как логическую функцию. Запишем в функциональном виде ту же конъюнкцию:
Элементарные высказывания и в этом случае играют роль аргументов (независимых переменных), которые в классической логике могут принимать 2 значения: истина или ложь. Далее для удобства я буду иногда называть простые высказывания переменными.
Таблица, описывающая логическую формулу (функцию) называется, как уже было озвучено, таблицей истинности. Пожалуйста – знакомая картинка:
Принцип формирования таблицы истинности таков: «на входе» нужно перечислить все возможные комбинации истины и лжи, которые могут принимать элементарные высказывания (аргументы). В данном случае в формулу входят два высказывания, и нетрудно выяснить, что таких комбинаций четыре. «На выходе» же получаем соответствующие логические значения всей формулы (функции).Надо сказать, что «выход» здесь получился «в один шаг», но в общем случае логическая формула является более сложной. И в таких «непростых случаях» нужно соблюдать порядок выполнения логических операций:
– в первую очередь выполняется отрицание ;
– во вторую очередь – конъюнкция ;
– затем – дизъюнкция ;
– потом импликация ;
– и, наконец, низший приоритет имеет эквиваленция .Так, например, запись подразумевает, что сначала нужно осуществить логическое умножение , а затем – логическое сложение: . Прямо как в «обычной» алгебре – «сначала умножаем, а затем складываем».
Порядок действий можно изменить привычным способом – скобками:
– здесь в первую очередь выполняется дизъюнкция и только потом более «сильная» операция.Наверное, все понимают, но на всякий пожарный: и – это две разные формулы! (как в формальном, так и в содержательном плане)
Составим таблицу истинности для формулы . В данную формулу входят два элементарных высказывания и «на входе» нам нужно перечислить все возможные комбинации единиц и нулей. Чтобы избежать путаницы и разночтений договоримся перечислять комбинации строго в таком порядке (который я, собственно, де-факто использую с самого начала):
В формулу входят две логические операции, и согласно их приоритету, в первую очередь нужно выполнить отрицание высказывания . Ну что же, отрицаем столбец «пэ» – единицы превращаем в нули, а нули – в единицы:
На втором шаге смотрим на столбцы и и применяем к ним операцию ИЛИ. Немного забегая вперёд, скажу, что дизъюнкция перестановочна ( и – это одно и то же), и поэтому столбцы можно анализировать в привычном порядке – слева направо. При выполнении логического сложения удобно использовать следующее прикладное рассуждение: «Если два нуля – ставим ноль, если хотя бы одна единица – единицу»:
Таблица истинности построена. А теперь вспомним старую-добрую импликацию:
…внимательно-внимательно… смотрим на итоговые колонки…. В алгебре высказываний такие формулы называются равносильными или тождественными:(три горизонтальные чёрточки – это значок тождества)
В 1-й части урока я обещал выразить импликацию через базовые логические операции, и выполнение обещания не заставило себя ждать! Желающие могут вложить в импликацию содержательный смысл (например, «Если идёт дождь, то на улице сыро») и самостоятельно проанализировать равносильное утверждение .
Сформулируем общее определение: две формулы называются равносильными (тождественными), если они принимают одинаковые значения при любом наборе значений, входящих в эти формулы переменных (элементарных высказываний). Также говорят, что «формулы равносильны, если совпадают их таблицы истинности», но мне не очень нравится эта фраза.
Составить таблицу истинности для формулы и убедиться в справедливости знакомого вам тождества .
Ещё раз повторим порядок решения задачи:
1) Так как в формулу входят две переменные, то всего будет 4 возможных набора нулей и единиц. Записываем их в оговорённом выше порядке.
2) Импликации «слабее» конъюнкции, но они располагаются в скобках. Заполняем столбец , при этом удобно использовать следующее прикладное рассуждение: «если из единицы следует ноль, то ставим ноль, во всех других случаях – единицу». Далее заполняем столбец для импликации , и при этом, внимание! – столбцы и следует анализировать «справа налево»!
3) И на завершающем этапе заполняем итоговый столбец . А здесь удобно рассуждать так: «если в столбцах и две единицы, то ставим единицу, во всех остальных случаях – ноль».
И, наконец, сверяемся с таблицей истинности эквиваленции .
Основные равносильности алгебры высказываний
С двумя из них мы только что познакомились, но ими дело, понятно, не огранивается. Тождеств довольно много и я перечислю самые важные и самые известные из них:
Коммутативность конъюнкции и коммутативность дизъюнкции
Коммутативность – это перестановочность:
Знакомые с 1-го класса правила: «От перестановки множителей (слагаемых) произведение (сумма) не меняется». Но при всей кажущейся элементарности этого свойства, справедливо оно далеко не всегда, в частности, некоммутативным является умножение матриц (в общем случае их переставлять нельзя), а векторное произведение векторов – антикоммутативно (перестановка векторов влечёт за собой смену знака).
И, кроме того, здесь я снова хочу подчеркнуть формализм математической логики. Так, например, фразы «Студент сдал экзамен и выпил» и «Студент выпил и сдал экзамен» различны с содержательной точки зрения, но неразличимы с позиций формальной истинности. …Таких студентов знает каждый из нас, и из этических соображений мы не будет озвучивать конкретных имён =)
Ассоциативность логического умножения и сложения
Или, если «по-школьному» – сочетательное свойство:
Дистрибутивные свойства
Обратите внимание, что во 2-м случае будет некорректно говорить о «раскрытии скобок», в известном смысле здесь «фикция» – ведь их можно убрать вообще: , т.к. умножение – это более сильная операция.
И опять же – эти, казалось бы, «банальные» свойства выполняются далеко не во всех алгебраических системах, и, более того, требуют доказательства (о которых мы очень скоро поговорим). К слову, второй дистрибутивный закон несправедлив даже в нашей «обычной» алгебре. И в самом деле:
Закон идемпотентности
Что делать, латынь.
Прямо какой-то принцип здоровой психики: «я и я – это я», «я или я – это тоже я» =)
И тут же несколько похожих тождеств:
…мда, что-то я даже подзавис… так и доктором философии завтра можно проснуться =)
Закон двойного отрицания
Ну а здесь уже напрашивается пример с русским языком – все прекрасно знают, что две частицы «не» означают «да». А для того, чтобы усилить эмоциональную окраску отрицания нередко используют три «не»:
– даже с крохотным доказательством получилось!Законы поглощения
– «а был ли мальчик?» =)
В правом тождестве скобки можно опустить.
Законы де Моргана
Предположим, что строгий Преподаватель (имя которого вам тоже известно:)) ставит экзамен, если – Студент ответил на 1-й вопрос и – Студент ответил на 2-й вопрос. Тогда высказывание , гласящее о том, что Студент не сдал экзамен, будет равносильно утверждению – Студент не ответил на 1-й вопрос или на 2-й вопрос.
Как уже отмечалось выше, равносильности подлежат доказательству, которое стандартно осуществляется с помощью таблиц истинности. В действительности мы уже доказали равносильности, выражающие импликацию и эквиваленцию, и сейчас настало время закрепить технику решения данной задачи.
Докажем тождество . Поскольку в него входит единственное высказывание , то «на входе» возможно всего лишь два варианта: единица либо ноль. Далее приписываем единичный столбец и применяем к ним правило И:
В результате «на выходе» получена формула, истинность которой совпадает с истинностью высказывания . Равносильность доказана.Да, это доказательство является примитивным (а кто-то скажет, что и «тупым»), но типичный Преподаватель по матлогике вытрясет за него душу. Поэтому даже к таким простым вещам не стОит относиться пренебрежительно.
Теперь убедимся, например, в справедливости закона де Моргана .
Сначала составим таблицу истинности для левой части. Поскольку дизъюнкция находится в скобках, то в первую очередь выполняем именно её, после чего отрицаем столбец :
Далее составим таблицу истинности для правой части . Здесь тоже всё прозрачно – в первую очередь проводим более «сильные» отрицания, затем применяем к столбцам правило И:
Результаты совпали, таким образом, тождество доказано.Любую равносильность можно представить в виде тождественно истинной формулы . Это значит, что ПРИ ЛЮБОМ исходном наборе нулей и единиц «на выходе» получается строго единица. И этому есть очень простое объяснение: так как таблицы истинности и совпадают, то, разумеется, они эквивалентны. Соединим, например, эквиваленцией левую и правую часть только что доказанного тождества де Моргана:
Или, если компактнее:Доказать следующие равносильности:
Краткое решение в конце урока. Не ленимся! Постарайтесь не просто составить таблицы истинности, но ещё и чётко сформулировать выводы. Как я недавно отмечал, пренебрежение простыми вещами может обойтись очень и очень дорого!
Продолжаем знакомиться с законами логики!
Да, совершенно верно – мы с ними уже вовсю работаем:
Формула, которая принимает значение Истина при любом наборе значений входящих в неё переменных, называется тождественно истинной формулой или законом логики.
В силу обоснованного ранее перехода от равносильности к тождественно истинной формуле , все перечисленные выше тождества представляют собой законы логики.
Формула, которая принимает значение Ложь при любом наборе значений входящих в неё переменных, называется тождественно ложной формулой или противоречием.
Фирменный пример противоречия от древних греков:
– никакое высказывание не может быть истинным и ложным одновременно.Доказательство тривиально:
«На выходе» получены исключительно нули, следовательно, формула действительно тождественна ложна.Однако и любое противоречие – это тоже закон логики, в частности:
Нельзя объять столь обширную тему в одной-единственной статье, и поэтому я ограничусь ещё лишь несколькими законами:
Закон исключённого третьего
– в классической логике любое высказывание истинно или ложно и третьего не дано. «Быть или не быть» – вот в чём вопрос.
Самостоятельно составьте табличку истинности и убедитесь в том, что это тождественно истинная формула.
Закон контрапозиции
Этот закон активно муссировался, когда мы обсуждали суть необходимого условия, вспоминаем: «Если во время дождя на улице сыро, то из этого следует, что если на улице сухо, то дождя точно не было».
Также из данного закона следует, что если справедливой является прямая теорема , то обязательно истинным будет и утверждение , которое иногда называют противоположной теоремой.
Если истинна обратная теорема , то в силу закона контрапозиции , справедлива и теорема, противоположная обратной:
И снова вернёмся к нашим содержательным примерам: для высказываний – число делится на 4, – число делится на 2 справедливы прямая и противоположная теоремы, но ложны обратная и противоположная обратной теоремы. Для «взрослой» же формулировки теоремы Пифагора истинны все 4 «направления».
Закон силлогизма
Тоже классика жанра: «Все дубы – деревья, все деревья – растения, следовательно, все дубы – растения».
Ну и здесь опять хочется отметить формализм математической логики: если наш строгий Преподаватель думает, что некий Студент – есть дуб, то с формальной точки зрения данный Студент, безусловно, растение =) …хотя, если задуматься, то может быть и с неформальной тоже =)
Давайте на этой веселой ноте проведём доказательство. В данную формулу входят уже элементарных высказывания , а значит, всего будет: различных комбинаций нулей и единиц (см. три левых столбца таблицы). Заодно, кстати, записал вам общую формулу; с точки зрения комбинаторики, здесь размещения с повторениями.
Составим таблицу истинности для формулы . В соответствии с приоритетом логических операций, придерживаемся следующего алгоритма:
1) выполняем импликации и . Вообще говоря, можно сразу выполнить и 3-ю импликацию, но с ней удобнее (и допустимо!) разобраться чуть позже;
2) к столбцам применяем правило И;
3) вот теперь выполняем ;
4) и на завершающем шаге применяем импликацию к столбцам и .
Не стесняйтесь контролировать процесс указательным и средним пальцем :))
Из последнего столбца, думаю, всё понятно без комментариев:
, что и требовалось доказать.Выяснить, будет ли являться законом логики следующая формула:
Краткое решение в конце урока. Да, и чуть не забыл – давайте условимся перечислять исходные наборы нулей и единиц в точно таком же порядке, что и при доказательстве закона силлогизма. Строки конечно, можно и переставить, но это сильно затруднит сверку с моим решением.
Преобразование логических формул
Помимо своего «логического» назначения, равносильности широко используются для преобразования и упрощения формул. Грубо говоря, одну часть тождества можно менять на другую. Так, например, если в логической формуле вам встретился фрагмент , то по закону идемпотентности вместо него можно (и нужно) записать просто . Если вы видите , то по закону поглощения упрощайте запись до . И так далее.
Кроме того, есть ещё одна важная вещь: тождества справедливы не только для элементарных высказываний, но и для произвольных формул. Так, например:
, где – любые (сколь угодно сложные) формулы.
Преобразуем, например, сложную импликацию (1-е тождество):
Далее применим к скобке «сложный» закон де Моргана, при этом, в силу приоритета операций, именно закон , где :
Скобки можно убрать, т.к. внутри находится более «сильная» конъюнкция:
Далее напрашивается использовать «простой» закон де Моргана и т.д.
Ну, а с коммутативностью вообще всё просто – даже обозначать ничего не нужно… что-то запал мне в душу закон силлогизма:))
Таким образом, закон можно переписать и в более затейливом виде:
Проговорите вслух логическую цепочку «с дубом, деревом, растением», и вы поймёте, что от перестановки импликаций содержательный смысл закона нисколько не изменился. Разве что формулировка стала оригинальнее.
В качестве тренировки упростим формулу .
С чего начать? Прежде всего, разобраться с порядком действий: здесь отрицание применено к целой скобке, которая «скреплена» с высказыванием «чуть более слабой» конъюнкцией. По существу, перед нами логическое произведение двух множителей: . Из двух оставшихся операций низшим приоритетом обладает импликация, и поэтому вся формула имеет следующую структуру: .
Как правило, на первом шаге (шагах) избавляются от эквиваленции и импликации (если они есть) и сводят формулу к трём основным логическим операциям. Что тут скажешь…. Логично.
(1) Используем тождество . А нашем случае .
Затем обычно следуют «разборки» со скобками. Сначала всё решение, затем комментарии. Чтобы не получилось «масло масляное», буду использовать значки «обычного» равенства:
(2) К внешним скобкам применяем закон де Моргана , где .
(3) К внутренним скобкам применяем закон двойного отрицания . Внешние скобки можно убрать, т.к. за её пределами находятся равные по силе операции.
(4) В силу коммутативности дизъюнкции меняем местами и . Оставшиеся скобки тоже убираем по озвученной выше причине.
(5) В силу коммутативности дизъюнкции меняем местами и , а также и .
(6) Используем закон идемпотентности и закон исключенного третьего
(7) Дважды используем тождество
Вот оно как…, оказалось, что наша формула – тожественно истинна:
Желающие могут составить таблицу истинности и убедиться в справедливости данного факта.
Наверное, все обратили внимание на формализм последних преобразований, но решать лучше именно так! В противном случае с немалой вероятностью гарантированы проблемы с зачётом задания (впрочем, тут от преподавателя зависит). Математическая логика как наука – формальна, и строго говоря, осуществлять «перескоки» наподобие нежелательно.
Пара задач для закрепления материала:
Выразить эквиваленцию через отрицание, конъюнкцию, дизъюнкцию и раскрыть скобки
Аккуратно проводим преобразования в соответствии с равносильностями. После этого будет не лишним вернуться к параграфу об эквиваленции и найти там фразу, которая соответствует полученному результату 😉
Упростить логическую формулу
Решения с подробными комментариями совсем близко.
И в заключение урока небольшое напутствие для читателей, которым предстоит погружение в матлогику. Данный предмет у меня был на 1-м курсе института, и в ходе изучения исчисления высказываний, предикатов и прочих «машин тьюринга» я допускал принципиальную ошибку – а именно, пытался «подогнать» под математическую логику неформальную основу. И окончательное понимание всей стройности формальной теории, важности «очевидных» доказательств и т.д. пришло далеко не сразу. Скучно? Нет! – на самом деле очень красиво…. То же самое, кстати, относится к высшей алгебре и некоторым другим предметам.
…но что бы вы прочитали эти строки, я всё-таки преподнёс материал, скорее в «школьном» стиле – с многочисленными содержательными примерами!
Решения и ответы:
Задание 1 Решение: составим таблицу истинности для формулы :
(подробные инструкции по заполнению таблицы находятся после условия задачи)
Полученный результат совпадает с эквиваленцией высказываний и , таким образом:Задание 2 Решение: доказательства проведём с помощью таблиц истинности:
а) Дважды записываем все варианты истины и лжи высказывания и применяем к столбцам операцию ИЛИ:
Результат совпадает с . Тождество доказаноб) составим таблицу истинности для левой части тождества
. Сначала к столбцам и применяем операцию ИЛИ, затем к столбцам и – операцию И:
В результате истинность формулы совпала с истинностью высказывания , таким образом, тождество доказано.Задание 3 Решение: составим таблицу истинности:
Вывод: данная формула не является тождественно истинной (законом логики)Задание 4 Решение:
(1) Используем тождество .
(2) Дважды применяем тождество .
(3) Используем дистрибутивный закон , в данном случае:
(квадратные скобки можно было не ставить – они не меняют порядок действий, но помогают лучше видеть ситуацию).
(4) В квадратных скобках используем коммутативность конъюнкции.
(5) Дважды используем тот же самый дистрибутивный закон.
(6) Во второй слева скобке используем коммутативность конъюнкции.
(7) Согласно закону противоречия: .
(8) К формуле дважды применяем тожество .
(9) А это уже для красоты :)) Скобки, кстати, можно было убрать намного раньше (я их не опускал с целью улучшить восприятие преобразований).Примечание: на 3-м шаге можно было раскрыть скобки по «правилу умножения многочленов» и сразу перейти к шагу № 7, но, строго говоря, это действие ещё нужно обосновать. А вдруг в алгебре логики это правило несправедливо?
Задание 5 Решение:
(1) Для левой скобки используем закон де Моргана. Во второй скобке – «раскладываем» импликацию.
(2) В первой скобке дважды применяем закон двойного отрицания. В силу коммутативности конъюнкции меняем местам и .
(3) К «иксу» и правой скобке применяем дистрибутивный закон.
(4) Согласно закону противоречия высказывания, средняя скобка тождественно ложна.
(5) К левой скобке применяем тождество . Убираем все скобки, поскольку это не меняет порядок действий.
(6) Используем коммутативность умножения и закон поглощения .Как определить тождественно истинное выражение?
Если при каждом наборе логических значений переменных, входящих в данное выражение, оно принимает истинное значение, то данное выражение называется тождественно—истинным или тавтологией. Тождественно – истинное выражение F обозначают: F≡1.
Тождественное преобразование выражения ( преобразование выражения) – это подмена одних выражений другими, тождественно равными друг другу. Для тождественных преобразований используют формулы сокращенного умножения, законы арифметики и другие тождества.
Два выражения, значения которых равны при всех допустимых значениях входящих в них переменных, называются тождественно равными выражениями. Два числовых выражения, имеющие одинаковые значения, также называются тождественно равными.
Также тождественно равными считаются такие числовые выражения, которым будут отвечать одни и те же значения. Это достаточно широкое определение, которое будет верным для всех целых выражений, смысл которых при изменении значений переменных не меняется.
Например, если a a будет равно 4 4, а b – 5 b – 5, то результаты все равно будут одинаковы. Еще один пример тождественно равных выражений с буквами – 0 ⋅x⋅ y ⋅z 0 · x · y · z и 0 0.
Какие высказывания называют тождественно истинными?
Доказать это можно составив таблицу истинности этих высказываний. Сложные высказывания, истинные при любых значениях входящих в них других высказываний, называются тождественно истинными, а высказывания, ложные при любых значениях входящих в них других высказываний, называются тождественно ложными.
Что значит тождественно истинное?
Тождественно-истинные высказывания — высказывания, выражения или формулы логических исчислений, являющиеся истинными при любых значениях истинности их переменных. Таковы все законы формальной логики. Соответственно тождественно-ложные высказывания или формулы ложны при любых значениях истинности их переменных.
Когда формула является тавтологией?
Формула называется Тавтологией, если она принимает только истинные значения при любых значениях букв. Другими словами, тавтология – это тождественно истинная формула.
Что такое формула в логике?
Выражением языка логики высказываний называют любую последовательность указанных символов. Некоторые из этих выражений объявляются правильно построенными. Их называют формулами. Формулы определяются следующими правилами, где буквы A, B …
Как определить тождественно истинное выражение? Ответы пользователей
Тождественно—истинные высказывания — высказывания, выражения или формулы логических исчислений, являющиеся истинными при любых значениях истинности их .
Приведенный выше пример является примером тождественно—истинной функции. Зная аналитическую форму логической функции, всегда можно перейти к табличной форме .
Определение значения истинности сложного высказывания» в курсе . Доказать, что логическое выражение является тождественно—истинным или .
Выражение А → В истинно если A ложно ИЛИ B истинно. То есть, А → В означает то же самое, что и (¬А) \/ В. См. таб. 4. 2) тождество .
(II) Истинностное значение сложного высказывания определяется только . В первом случае она называется тавтологией (тождественно истинным высказыванием), .
3) только те выражения являются формулами логики высказываний, для которых это следует из 1) и 2). Определение формулы логики высказываний содержит перечисление .
Истинно ли высказывание «Разные логические выражения могут определять одну и ту же . Пример тождественно истинного выражения: А + А, пример тождественно .
Истинность или ложность высказывания определяется вне алгебры логики — с . называется тождественно–истинным выражением (тавтологией).
Составьте и запишите истинные сложные высказывания из простых с использованием логических операций. Неверно, что 10>Y>5 и Z
Как определить тождественно истинное выражение? Видео-ответы
Урок 5 ТОЖДЕСТВА. ТОЖДЕСТВЕННЫЕ ПРЕОБРАЗОВАНИЯ ВЫРАЖЕНИЙ 7 КЛАСС
учимдома #сидимдома #видеоурок #миниурокипоматематике Видеоурок по теме тождества и тождественные .
Тождества. Тождественные преобразования выражений. 6 класс.
тождества #MEKTEП_OnLine #MEKTEP_OnLine Образовательный сайт: https://mektep-online.kz/ .
Конъюнкция, дизъюнкция, импликация, эквиваленция, отрицание. На примерах из жизни. Логика.
Хочешь записать на курс от информатика БУ? Пиши сюда https://vk.me/inf_bu Ответим на все вопросы, .
Выражение и его значение. Порядок выполнения действий | Математика 4 класс #2 | Инфоурок
Видеоуроки являются идеальными помощниками при изучении новых тем, закреплении материала, для обычных и .