Как определить тождественно истинное выражение?
Если при каждом наборе логических значений переменных, входящих в данное выражение, оно принимает истинное значение, то данное выражение называется тождественно—истинным или тавтологией. Тождественно – истинное выражение 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 | Инфоурок
Видеоуроки являются идеальными помощниками при изучении новых тем, закреплении материала, для обычных и .
Тождественно-истинное высказывание
высказывание, которое при любых значениях простых суждений, входящих в его состав, имеет значение «истинно». Такие высказывания называют также тавтологиями, а формулы, которые им соответствуют, — тождественноистинными формулами или законами логики.
- Telegram
- Вконтакте
- Одноклассники
Научные статьи на тему «Тождественно-истинное высказывание»
Исчисление высказываний
Также не являются высказываниями фразы, для которых невозможно установить их истинность.
Классическое исчисление высказываний оперирует двумя истинностными значениями: 0 – ложь, 1 – истина.
Определение 3 Логикой высказываний называют раздел логики, в котором вопрос о ложности или истинности.
Тождественно истинные формулы Определение 5 Формулу исчисления высказываний называют тождественно.
Примерами тождественно истинных формул, имеющих большое значение для логики высказываний, являются:
Представление импликативной условной связи посредством объединения ее видов
Различается импликация как двузначный, двуместный функтор α (φ, ψ), где φ, ψ простые высказывания и импликативно условная связь высказываний (φ→ψ). Импликация α(φ,ψ) не означает, что (φ→ψ); (φ→ψ) только и если только α (φ, ψ) тождественно истинное. Не всё, что говорится о α (φ, ψ), можно сказать относительно (φ→ψ). Например, α (φ, ψ) для любых высказываний равно (⌐φ ˅ ψ), где ⌐ отрицание, а ˅ дизъюнкция, в то время как (φ→ψ) не равно (⌐φ ˅ ψ). Принимается система высказываний G, в которой вопрос о представлении функции (φ→ψ) через другие функции решен. При этом определяются значения для высказываний из G любой степени сложности. Так, два высказывания φ (x1, x2, …, xn) и ψ (x1, x2, …, xn) G-множества определяются как формально независимые на М, если и только если для любых пакетов значений их аргументов (а1, а2, …, аn), где ai принадлежит М (для i от 1 до n), выражение (φψ) может принимать только следующие значения истинности-ложности: или (11), или (10), или (01), или (00). Всего вы.
Неправильные логические рассуждения
, а тождественные – за различные.
Этот принцип может быть определен по-разному: ни одно высказывание не может быть одновременно истинным.
не могут быть одновременно истинными высказывание и его отрицание.
Закон исключенного третьего (принцип, который обуславливает истинность высказываний).
В современной формулировке он звучит так: «Истинно или само высказывание, или его отрицание».
Уточнение списка аристотелевских силлогизмов
Обосновывается ошибочность, по крайней мере, в той части, где речь идет о принимаемости силлогистических формул на основе их Х-матриц, тезиса о том, что из утвердительных простых категорических высказываний нельзя получить отрицательное высказывание. В статье предъявлены два аристотелевских силлогизма ApmAmsOsp и AmsApmOsp, в которых истинность посылок гарантирует истинность заключений при условии запрета подставлять в них вместо s, p, m тождественные общие имена. Указанные силлогизмы ошибочно относят к множеству «неправильных», а потому не принимаемых, отбрасываемых формул аристотелевской силлогистики. Полученные результаты позволяют обнаружить «утерянные» законы аристотелевской силлогистики: найдена формула AspOsp, имеющая такую же Х-матрицу, как и законы обращения или подчинения для выражений вида Asp, Isp, Esp, Osp. Эту формулу уместно называть вторым законом обращения общеутвердительных высказываний. Формулы ApmAmsOsp, AmsApmOsp, AspOps трудно найти, но они легко доказываются с.
Табличное построение логики высказываний. Тождественно-истинные, тождественно-ложные и выполнимые формулы.
Построим таблицу истинности для формулы, имеющей в своем составе одну пропозициональную переменную: рÉùp. В таблице под главным знаком (главной логической константой) формулы пишутся истинностные значения формулы в целом. В данной формуле главным знаком является знак импликации, соответственно истинностные значения данной формулы будут находиться под ним:
Пример таблицы истинности для формулы ù (pÉq) º (q&ùp), имеющей в своем составе две пропозициональные переменные:
Пример таблицы истинности для формулы (pÉq)É((qÉr)É(pÉr)), имеющей в своем составе три пропозициональные переменные:
иии и иии и иии
иии и илл и илл
илл и лии и иии
илл и лил л илл
лии и иии и лии
лии и илл и лил
лил и лии и лии
лил и лил и лил
Последняя формула под главным знаком принимает восемь значений “истина” из восьми возможных. Это означает, что она является логическим законом.
Формула называется тождественно-истинной (или законом классической логики высказываний), если она принимает значение “истина” при любых наборах значений входящих в нее пропозициональных переменных.
Формула называется тождественно-ложной, если и только если она принимает значение “ложь” при при любых наборах значений входящих в нее пропозициональных переменных.
Формула называется выполнимой, если существует набор значений входящих в нее пропозициональных переменных, при котором она принимает значение “истина”.
Ввиду вышесказанного все высказывания естественного языка можно подразделить на три группы:
Логически истинные (истинные в силу своей логической формы).
Логически ложные (ложные в силу своей логической формы).
Логически недетерминированные (их истинность или ложность зависит от нелогических обстоятельств).
Алгебра логики
Функции тождественны, если $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\
,\dots,\overline )=\overline \right\>$. - $M$ монотонных функций: $M=\left\
$. - $L$ линейных функций: $L=\left\
\right\>$.
Ни один из предполных классов не содержится целиком в объединении четырёх остальных; любой замкнутый класс булевых функций, отличный от $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$ конечное число, их можно перебрать.
Конъюнкция — пересечение областей определения, дизъюнкция — объединение областей определения, отрицание — дополнение области определения.
Кванторы по предикатным переменным
Правило отрицания кванторов: применяется для построения отрицаний высказываний, содержащих кванторы, и имеет вид: