Питон и таблицы истинности
Таблица истинности — это таблица, где перечисляются комбинации аргументов некой логической функции и указывается, какие значения принимает эта функция.
В задаче 2 ЕГЭ по информатике требуется 1) уметь строить таблицы истинности логического выражения и 2) уметь сравнивать построенную таблицу истинности с таблицей, приведенной в условии задачи.
Первый пункт можно выполнить на компьютере, написав несложную (менее 10 строк) программу на Питоне.
Вообще говоря, в Питоне, как и в паскале, есть специальные логические значения True и False. Но в логических выражениях можно использовать и числа. При этом значение 0 считается ложью, а всё, отличное от нуля — истиной. (Тут создатель Питона позаимствовал идею из С.)
Рассмотрим задачу с сайта «Решу ЕГЭ». В ней требуется сопоставить переменные, входящие в логическую функцию
| Переменная 1 | Переменная 2 | Переменная 3 | Переменная 4 | Функция |
|---|---|---|---|---|
| . | . | . | . | F |
| 1 | — | — | 1 | 0 |
| 1 | — | — | — | 0 |
| — | 1 | — | 1 | 0 |
Требуется выяснить, какая переменная в таблице обозначена как «переменная 1», «переменная 2» и т.д.
Из последнего столбца видно, что нам нужны те комбинации значений переменных, при которых функция ложна.
Так как в Питоне отсутствует логическая операция импликации, заменяем выражения вроде x → y на эквивалентные выражения not x or y. Операция эквивалентности — это сравнение «= ложь»:
for x in range(2):
for y in range(2):
for z in range(2):
for w in range(2):
f = ((not x or y ) and (not y or w)) or (z == ( x or y))
if not f: print(x,y,z,w)
Программа печатает следующую таблицу:
0 1 0 0
1 0 0 0
1 0 0 1
1 1 0 0
Столбцы слева направо — это значения переменных x, y, z, w соответственно.
Таким образом, мы очень упростили первую часть задачи — построение таблицы истинности. Осталась вторая часть.
В нашей таблице четыре строки, а в задаче — только три. Следовательно, одна строка в нашей таблице лишняя.
Заметим, что в таблице из задачи пять единиц, а в нашей таблице — шесть. Отсюда вытекают два вывода. Во-первых, мы не можем удалить из нашей таблицу строчку с двумя единицами — тогда у нас их останется четыре, т.е. менее, чем в таблице из задачи. Во-вторых, при удалении из нашей таблицы строки с одной единицей и в нашей таблице, и в таблице из задачи будет по пять единиц. Следовательно, во всех пустых клетках таблицы из задачи записаны нули.
Самую первую строку из нашей таблицы удалить нельзя: тогда у нас появляется столбец из трёх единиц, а такого столбца в таблица из задачи нет. Убираем вторую строку и получаем следующую таблицу:
0 1 0 0
1 0 0 1
1 1 0 0
В столбце переменной z — только нули. Следовательно, в задаче переменная 3 — это z.
В столбце переменной w только одна единица. Следовательно, переменная w — это переменная 2 в задаче.
Замечаем, что когда переменная w (переменная 2 в задаче) равна 1, то равна 1 также и переменная x (а в задаче это переменная 4). Следовательно, переменная 4 — это x. Оставшаяся переменная 1 — это переменная y.
Итак, наш ответ — ywzx. Именно такой ответ и приводится в задаче.
При записи логических выражений в Питоне можно столкнуться с тем, что выражения вроде (x ≡ ¬z) при буквальном их переводе (x == not z) вызывают синтаксическую ошибку. Чтобы избежать этого, надо либо заключить выражение not z в дополнительные скобки, т.е. написать (x == (not z)). Можно также заменить операцию «равно» на «не равно», т.е. записать это выражение как (x != z).
Булева алгебра и построение логических схем. Логические и битовые операции: AND, OR, NOT, XOR — таблицы значений
Математическая логика изучает методы и средства оперирования логическими формулами (выражениями). В этом уроке мы изучим обозначения, синтаксис (грамматику) и семантику (значение) различных логических выражений.
Высказывание и операции над высказыванием
Исходным (базовым) понятием является простое высказывание.
Под высказыванием обычно понимают всякое предположение, утверждающее что-либо о чем-либо. Если смысл, содержащийся в высказывании, соответствует действительности, то высказывание является истинным, иначе ложным.
Обычно элементарные высказывания обозначают строчными буквами латинского алфавита $a$, $b$, $c$, $x$, $y$ …, которые являются логическими переменными в логических формулах. Истинные значения обозначаются буквой И (True, T) или 1, а ложные – Л (False, F) или 0.
Унарные функции
$n = 1$ — количество аргументов. $k_n = 2^n = 2$ $k_ф = 2$
Бинарные функции
$n = 2$ — количество аргументов. $k_n = 2^2 = 4$ $k_ф = 2^4 = 16$
| $x$ | $y$ | $f_0$ | $f_1$ | $f_2$ | $f_3$ | $f_4$ | $f_5$ | $f_6$ | $f_7$ | $f_8$ | $f_9$ | $f_<10>$ | $f_<11>$ | $f_<12>$ | $f_<13>$ | $f_<14>$ | $f_<15>$ |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| const «0» | $x \land y$ | пер. $x$ | пер. $y$ | $x \xor y$ | $x \lor y$ | const «1» |
Номер функции совпадает с двоичной записью функции
- $f_1$ — коньюнкция. $x \& y$ — $x$ и $y$ — $
and $ $x \&\& y$ - $f_7$ — дизъюнкция. $x | y$ — $x$ или $y$
- $f_<11>$ и $f_<13>$ — импликация (следование)
- $f_9$ — равнозначность, эквивалентность, равносильность. $
\equiv $ - $f_6$ — равнозначность, эквивалентность, равносильность. $
\equiv $
Из элементарных высказываний можно составить более сложные с помощью логических связок:
- $\lnot$ — логическое "не" (отрицание)
- $\land$ — логическое "и" (конъюнкция) — «и одновременно»
- $\lor$ — логическое "или" (дизъюнкция)
- $\Rightarrow$ — "логическое следствие" (импликация)
- $\equiv$ — "эквивалентность"
- круглых скобок (, ) — групировка операций.
- . есть и другие (менее распространённые) связки.
Логические связки можно определить с помощью таблицы истинности. В левой части этой таблицы перечисляются все возможные комбинации значений логических переменных $x$ и $y$. В правой части – соответствующие им им значения выражений из переменных и логических связок.
| $x$ | $y$ | $\lnot x$ | $x \land y$ | $x \lor y$ | $x \Rightarrow y$ | $x \equiv y$ |
| 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 |
Связки имеют следующий приоритет: $\lnot \land \lor \Rightarrow \equiv$ (приоритет можно изменить с помощью скобок). Высказывания (формулы) из простых высказываний, связок и скобок, называют правильно построенными формулами или просто формулами.
Значение логических связок близко к соответствующим высказываниям на естественном языке. Например смысл связок $\lnot$ и $\land$ практически совпадает со смыслом слов «не» и «и». Однако имеются и некоторые различия. Так формула $x \lor y$ несколько шире, чем русское «$x$ или $y$». Выражение «$x$ или $y$» по смыслу это формула $x \land \lnot y \lor \lnot x \land y$ (исключающее или). Еще больше различий между семантикой формулы $x \Rightarrow y$ в логике высказываний и выражению «из $x$ следует $y$». В русском языке это выражение истинно, если истинны $x$ и $y$, т.е. предложение русского языка по смыслу совпадает с формулой $x \land y$. Логическое следствие истинно также, если $x$ и $y$ ложны или $x$ ложна, а $y$ истинна. Логическую формулу $x \Rightarrow y$ следует интерпретировать на естественном языке так: «Если $x$ истинна, то $y$ тоже истинна, а остальное неизвестно».
Таблица истинности — таблица в которой в левой части перечислены все возможные значения переменных, а в правой части значения функции. Для построения таблицы истинности выписываются все возможные значения аргументов, а потом поэтапно вычисляем значения.
Для любой формулы также можно написать таблицу истинности. Например:
| $x$ | $y$ | $\lnot x$ | $\lnot y \lor y$ | $\lnot x \land (\lnot y \lor y)$ | $\lnot x \land (\lnot y \lor y) \Rightarrow \lnot x$ |
| 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 | 1 |
Если формула содержит $n$ переменных, то в таблице истинности будет $2^n$ строк (в примере формула содержит 2 переменные и $2^2 = 4$ строки). Кроме того, данная формула истинна на любом наборе значений своих переменных (везде 1). Такие формулы называются тождественно истинными или тавтологиями. В противоположной ситуации, формула является тождественно ложной или невыполнимой. Если две разные формулы принимают одинаковые значения на любом наборе значений переменных, то такие формулы называют равносильными. Равносильные формулы обозначаются знаком равенства =.
Законы алгебры логики
В логике высказываний известно много общезначимых формул, которые также называются законами логики высказываний. Основными законами являются следующие:
- законы идемпотентности (повторение действия над объектом не изменяет его, латинский idem — «тот же самый» и potens — «способный»):
- $x \land x = x$
- $x \lor x = x$
- $x \land (y \lor x) = x$
- $x \lor (y \land x) = x$
Доказать эти и последующие законы можно с помощью построения таблиц истинности или простейших логических рассуждений.
Следующая группа законов представляет взаимосвязь между логическими операциями:- $(x \equiv y) = (x \Rightarrow y) \land (y \Rightarrow x)$
- $x \Rightarrow y = \lnot x \lor y$
- законы Де Моргана
- $\lnot(y \lor x) = \lnot y \land \lnot x$
- $\lnot(y \land x) = \lnot y \lor \lnot x$
Замечательным следствием приведенных выше законов является следующий факт. Любую логическую формулу можно заменить равносильной ей, но содержащую только две логические операции:
- конъюнкцию "и" и отрицание "не"
- дизъюнкцию "или" и отрицание "не"
Дальнейшее исключение логических операций, очевидно, невозможно, то есть приведенные пары представляют минимальный базис для построения правильно построенных формул. Однако существует операция, с помощью которой можно представить любую логическую связку. Эта операция получила название «штрих Шеффера» и определяется следующим образом:
$x$ $y$ $x | y$ 0 0 1 0 1 0 1 0 0 1 1 0 На основании этого определения можно ввести следующие законы, выражающие взаимосвязь операции «штрих Шеффера» и других логических связок:
- $\lnot x = x | x$ — связка «не» через «штрих Шеффера»
- $x \land y = (x | y) | (x | y)$ — связка «и» через «штрих Шеффера»
Также следует отметить, что $x | y= \lnot (x \lor y)$.
К основным законам алгебры логики также относятся следующие:- коммутативные законы (от перестановки мест результат не меняется)
- $x \land y = y \land x$
- $х \lor y = y \lor x$
- $x \land (y \lor z) = (x \land y) \lor (x \land z)$
- $x \lor (y \land z) = (x \lor y) \land (x \lor z)$
- $x \land (y \land z) = (x \land y) \land z$
- $x \lor (y \lor z) = (х \lor y) \lor z$
С помощью законов логики можно осуществлять равносильные преобразования. Такие преобразования используются для доказательств, приведения формул к заданному виду, упрощения формул.
Под сложностью формул обычно понимается количество символов, используемых для ее записи. То есть формула $\alpha$ проще формулы $\beta$, если $\alpha$ содержит меньше букв и логических операций. Например, для формулы $(\lnot (x \lor y) \Rightarrow x \lor y) \land y$ можно записать следующую цепочку преобразований, приводящих ее к более простому виду:
$(\lnot \lnot(x \lor y) \lor x \lor y) \land y = (x \lor y \lor x \lor y) \land y = (x \lor y) \land y = y$.
Операция XOR
Операция XOR — это операция "побитное не равно" или сложение по модулю 2 для отдельных битов, в логике обозначается $x \oplus y$.
Задача "Повторные числа"
Входной файл содержит большое число чисел (целых или действительных) или строк, среди них все повторяются чётное число раз, и только одно — нечётное число раз. Вывести то, которое повторяется нечётное число раз.
Решение: завести переменную нужного типа, инициализировать её нулями, выполнять операцию XOR с каждым новым числом (строкой), в результате останется только число (строка), встречающаяся нечётное число раз.
Вычисление значения логического выражения
Для вычисления значения логического выражения мы можем просто поставить (replace) переменные как значения, потом прогнать все операции с наибольшим приоритетом (логическое НЕ, затем И), затем в операциях с меньшим приоритетом (ИЛИ).
Как обозначается импликация?
d) следование (импликация) обозначается → (например, А → В); e) тождество обозначается ≡ (например, A ≡ B). Выражение A ≡ B истинно тогда и только тогда, когда значения A и B совпадают (либо они оба истинны, либо они оба ложны);
Импликация (от лат. implicatio — «связь») — бинарная логическая связка, по своему применению приближенная к союзам «если…, то…». Импликация записывается как посылка
Суждение, выражаемое импликацией, выражается также следующими способами : следствие является условием, необходимым для истинности посылки. Импликация играет очень важную роль в умозаключениях. С её помощью формулируются определения различных понятий, теоремы, научные законы .
Импликация записывается как посылка следствие; применяются также стрелки другой формы и направленные в другую… … Википедия ИМПЛИКАЦИЯ — ИМПЛИКАЦИЯ, логическое высказывание типа «если Р, то Q», соединяющее два элементарных высказывания Р (антецедент) и Q (логическое следствие).
Впрочем, такое представление отрицания возможно и в классической логике. В интуиционистской теории типов импликации соответствует множество (тип) отображений из A в B. В учении о силлогизмах импликации отвечает «общеутвердительное атрибутивное высказывание».
Как записывается импликация?
Импликация читается: «если A, то B», или «из A следует B»; записывается: A → B (здесь высказывание A называется посылкой высказывания A → B, а высказывание B — его заключением, для записи применяются также стрелки другой формы, но всегда указывающие на соотношение посылка → следствие), другое обозначение импликации: A .
Как написать Импликацию в Питоне?
Основы программирования на Python импликация (в математике обозначается как a => b , в Python можно выразить как not(a) or b )
Каким знаком обозначается инверсия?
Отрица́ние (инве́рсия, от лат. inversio — переворот, логи́ческое «НЕ») в логике — унарная операция над суждениями, результатом которой является суждение, «противоположное» исходному. Обозначается знаком ¬ перед или чертой — над суждением.
Как обозначается импликация в информатике?
d) следование (импликация) обозначается → (например, А → В); e) тождество обозначается ≡ (например, A ≡ B). Выражение A ≡ B истинно тогда и только тогда, когда значения A и B совпадают (либо они оба истинны, либо они оба ложны);
Чем можно заменить импликацию?
Импликацию можно заменить на выражение, использующее ранее изученные операции НЕ и ИЛИ: — Логическая операция, ставящая в соответствие двум высказываниям новое, являющееся истинным тогда и только тогда, когда только одно из двух высказываний истинно, называется строгой (исключающей) дизъюнкцией.
Что означает в Питон?
Оператор =. Это классический оператор присваивания. Обратите внимание, он не проверяет равенство операндов, за это отвечает другой оператор. Он именно используется для присваивания значений или объектов переменным.
Как в Питоне обозначается дизъюнкция?
В языке Питон оператор «логическое И» обозначается словом and . Логическое ИЛИ: результатом этой операции будет истина тогда, и только тогда, когда хотя бы одна из величин x или y истинна. В математике эта операция называется дизъюнкцией и обозначается x v y.
Что такое результат импликации?
Импликация (лат. implicatio — связь) — бинарная логическая связка, по своему применению приближенная к союзам «если… то…». следствие; применяются также стрелки другой формы и направленные в другую сторону (остриё всегда указывает на следствие).
Как обозначается импликация? Ответы пользователей
Импликация — это логическая операция, принятая в формализованных языках (см. Язык формализованный) для образования сложных высказываний (формул) из элементарных .
В логических формулах импликация обозначается знаком ->. Операция A -> B определяет логическую функцию, тождественно совпадающую с функцией !A || B.
Импликация (лат. implicatio — связь) — бинарная логическая связка, . Импликация обозначается символом ⇒, и ей соответствует вложение множеств: пусть A .
Эта отметка установлена 30 ноября 2016 года. Теория множеств. Импликация высказываний означает, что одно из них следует из другого. Импликация обозначается .
Основные логические операции (конъюнкция, дизъюнкция, инверсия, импликация, эквивалентность), их определния, примеры, для каждой логической операции .
Примерами Л. о. являются дизъюнкция, конъюнкция, импликация, отрицание, . В формализованных языках импликация высказываний A и B обозначается A⇒B [а .
Глоссарий по теме: импликация, эквиваленция, предикат, примеры законов алгебры . Операция импликации обозначается символом и задается следующей таблицей .
В логических формулах импликация обозначается знаком ->. Операция A -> B определяет логическую функцию, тождественно совпадающую с функцией!
Логические операции и их свойства
Конъюнкция или логическое умножение (в теории множеств – это пересечение)
Конъюнкция является сложным логическим выражением, которое истинно в том и только том случае, когда оба простых выражения являются истинными. Такая ситуация возможно лишь в единственном случае, во всех остальных случаях конъюнкция ложна.
Обозначение: &, $\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$ строк.