Как заменить следование в информатике

Питон и таблицы истинности

Булева алгебра и построение логических схем. Логические и битовые операции: AND, OR, NOT, XOR — таблицы значений

Высказывание и операции над высказыванием

Законы алгебры логики

Унарные функции

Бинарные функции

Таблица истинности — это таблица, где перечисляются комбинации аргументов некой логической функции и указывается, какие значения принимает эта функция.

В задаче 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).

Математическая логика изучает методы и средства оперирования логическими формулами (выражениями). В этом уроке мы изучим обозначения, синтаксис (грамматику) и семантику (значение) различных логических выражений.

Исходным (базовым) понятием является простое высказывание.

Под высказыванием обычно понимают всякое предположение, утверждающее что-либо о чем-либо. Если смысл, содержащийся в высказывании, соответствует действительности, то высказывание является истинным, иначе ложным.

Обычно элементарные высказывания обозначают строчными буквами латинского алфавита $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$. В правой части – соответствующие им им значения выражений из переменных и логических связок.

Связки имеют следующий приоритет: $\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). Такие формулы называются тождественно истинными или тавтологиями. В противоположной ситуации, формула является тождественно ложной или невыполнимой. Если две разные формулы принимают одинаковые значения на любом наборе значений переменных, то такие формулы называют равносильными. Равносильные формулы обозначаются знаком равенства =.

$x \land y$

$x \lor y$

$x \Rightarrow y$

$x \equiv y$

В логике высказываний известно много общезначимых формул, которые также называются законами логики высказываний. Основными законами являются следующие:

законы идемпотентности (повторение действия над объектом не изменяет его, латинский 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) переменные как значения, потом прогнать все операции с наибольшим приоритетом (логическое НЕ, затем И), затем в операциях с меньшим приоритетом (ИЛИ).
    
    Задание 2 ЕГЭ по информатике. Таблицы истинности
    
    Логическое выражение — это утверждение или комбинация утверждений, которые могут быть истинными (true) или ложными (false).
    
    Примеры логических выражений:
    - x > y (x больше, чем y)
    - a == b (a равно b)
    - (x > 5) && (y < 10) (x больше 5 и y меньше 10)
    - (a != b) || (c == d) (a не равно b или c равно d)
    Логические выражения могут быть использованы в различных языках программирования, таких как Java, Python, C++ и других. Они играют важную роль в управлении потоком выполнения программы и помогают программистам создавать более гибкие и мощные программы.
    
    Логические операции
    
    Логические операции — это операции, которые выполняются над логическими выражениями и результатом их выполнения является новое логическое выражение.
    
    В программировании, логические операции обычно выполняются над булевыми значениями (true/false).
    
    Примеры логических операций:
    - Операция «И» (AND),конъюнкция: обозначается символом && или * или ∧, возвращает true только если оба операнда равны true. Например, «сходить в магазин И купить молоко» — будет выполнено только если оба условия верны.
    - Операция «ИЛИ» (OR), дизъюнкция: обозначается символом || или + или ∨, возвращает true, если хотя бы один из операндов равен true. Например, «если завтра будет солнечно ИЛИ я не буду занят — я поеду на пикник» — здесь выполнение произойдет если хотя бы одно из условий верно.
    - Операция «НЕ» (NOT), отрицание: обозначается символом ! или ¬, инвертирует логическое значение операнда (true становится false, и наоборот). Например, «не пойду в кино» — значение станет true, если изначально мы планировали пойти в кино, а после применения NOT мы получим отрицание этого утверждения — что мы не пойдем.
    - Тождественное равенство — это логическая операция, которая используется для проверки равенства двух логических выражений во всех возможных случаях. Она обозначается как «≡» или как «==» в некоторых языках программирования. Результат тождественного равенства является логическим значением истинности (true) или ложности (false). Например, выражение «x = y ≡ y > x» вернет значение false.
    - Импликация (следование) — это логическая операция, которая определяет, как одно логическое выражение влияет на другое. Она обозначается как «→» или как «->» в некоторых языках программирования. Импликация говорит о том, что если одно выражение (предпосылка) является истинным, то другое выражение (заключение) также является истинным. Если же предпосылка ложна, то заключение может быть как истинным, так и ложным. Например, выражение «если я поеду в отпуск, то я возьму с собой книги» может быть записано как «поездка в отпуск → взятие книг». Если я поеду в отпуск, то я обязательно возьму с собой книги. Но если я не поеду в отпуск, то я могу взять книги или не брать их в зависимости от других факторов.
    Примеры логических операций в повседневной жизни:
    - «Если сегодня пятница И я не занят, то я поеду на вечеринку». Здесь операция «И» используется для определения условий, при которых мы поедем на вечеринку.
    - «Если я буду дома ИЛИ будет идти дождь, то я останусь дома». Здесь операция «ИЛИ» используется для определения условий, при которых мы останемся дома.
    - «Я НЕ буду есть мясо, потому что я вегетарианец». Здесь операция «НЕ» используется для инвертирования утверждения о том, что мы будем есть мясо.
    Таблица истинности логических выражений
    
    Таблица истинности — это таблица, которая показывает все возможные значения истинности логического выражения в зависимости от значений его логических компонентов (переменных). В таблице истинности для каждого возможного набора значений переменных указывается, является ли исходное логическое выражение истинным или ложным.
    
    Обычно, в такой таблице, вместо логических значений False и True (Ложь и Истина), используются значения 0 (False) и 1 (True).
    
    Рассмотрим пример таблицы истинности для простого выражения из одной логической операции — операции отрицания (NOT). Пусть дана переменная x, которая может принимать значения true или false. Тогда таблица истинности для операции отрицания выглядит следующим образом:
    
    x NOT x
    
    0 1
    
    1 0
    
    Как видно из таблицы, если x равно true (1), то NOT x будет равно false (0), а если x равно false (0), то NOT x будет равно true (1).
    
    Теперь рассмотрим пример более сложного логического выражения, которое включает в себя несколько логических операций. Пусть даны две переменные x и y, которые могут принимать значения true или false. Рассмотрим логическое выражение «x AND (NOT y)». Таблица истинности для этого выражения будет выглядеть следующим образом:
    
    x y NOT y x AND (NOT y)
    
    0 0 1 0
    
    0 1 0 0
    
    1 0 1 1
    
    1 1 0 0
    
    Как видно из таблицы, выражение «x AND (NOT y)» будет истинным только в том случае, если x равно true, а y равно false. Если хотя бы одна из переменных равна false, то исходное выражение будет ложным.
    
    Таблицы истинности для конъюнкции, дизъюнкции, импликации
    
    Конъюнкция, дизъюнкция и импликация — это три основные бинарные логические операции. Бинарные логические операции работают с двумя логическими выражениями (условиями) и возвращают результат в виде одного логического значения — истинности или ложности.
    
    Таблицы истинности для этих операций выглядят следующим образом:
    
    Конъюнкция (AND)
    
    A B A AND B
    
    0 0 0
    
    0 1 0
    
    1 0 0
    
    1 1 1
    
    В таблице истинности для конъюнкции, результат будет истинным только в том случае, если оба условия истинны.
    
    Дизъюнкция (OR)
    
    A B A OR B
    
    0 0 0
    
    0 1 1
    
    1 0 1
    
    1 1 1
    
    В таблице истинности для дизъюнкции, результат будет истинным, если хотя бы одно из условий истинно.
    
    Импликация (IF-THEN)
    
    A B A → B
    
    0 0 1
    
    0 1 1
    
    1 0 0
    
    1 1 1
    
    В таблице истинности для импликации, если условие A истинно, то результат будет истинным только в том случае, если условие B тоже истинно. Если же условие A ложно, то результат всегда будет истинным, независимо от того, что является условием B.
    
    Приоритет логических операций
    
    Приоритет логических операций — это порядок, в котором операции выполняются в логическом выражении.
    
    Если в выражении присутствуют несколько операций, то порядок их выполнения зависит от приоритета операций.
    
    В общем случае, порядок выполнения операций в выражении определяется следующими правилами:
    1. Сначала выполняются операции в скобках.
    2. Затем выполняются операции логического отрицания (NOT).
    3. Затем выполняются операции логического умножения (AND).
    4. Затем выполняются операции логического сложения (OR).
    5. В конце выполняются операции импликации (IF-THEN) и эквивалентности (IF AND ONLY IF).
    Таким образом, операции в логическом выражении выполняются в порядке убывания приоритета.
    
    Например, в выражении «A OR B AND C» операция AND выполнится первой, так как у нее приоритет выше, чем у операции OR. Однако, если требуется изменить порядок выполнения операций, можно использовать скобки, например: «(A OR B) AND C». В этом случае, операция OR выполнится первой, а затем результат будет умножен на C, так как операция AND имеет более высокий приоритет, чем операция OR.
    
    Важно помнить, что правильный порядок выполнения операций в выражении может значительно влиять на его результат, поэтому при работе с логическими выражениями важно следить за приоритетом операций и правильно использовать скобки.
    
    Построение таблиц истинности логических выражений с помощью Python
    
    Чтобы построить таблицу истинности логического выражения, нам понадобятся знания и навыки из урока по циклам в Python.
    
    Если вы не разбирали данный урок, то обязательно начните прямо сейчас! И лишь после этого, возвращайтесь к изучению данного материала.
    
    Особенное внимание уделите таким темам как:
    
    Построение таблицы истинности для конъюнкции трех условий.
    
    Для построения таблицы истинности для конъюнкции трех условий можно воспользоваться языком программирования Python и его возможностью работы с логическими операциями.
    
    Для создания всех возможных комбинаций 0 и 1 (истинных и ложных значений), воспользуемся тройным вложенным циклом for Каждый цикл перебирает два возможных значения ( 0 и 1 ) для каждого из операндов: x , y , z
    
    Для этого можно написать следующий код:
    
    В данном коде мы задаем начальные значения переменных a, b и c как False. Затем мы выводим заголовок таблицы истинности и перебираем все возможные значения переменных a, b и c, используя вложенные циклы. Для каждой комбинации значений переменных мы вычисляем значение выражения и выводим результат в таблицу. В конце каждой строки таблицы мы переходим на новую строку с помощью команды `print()`.
    
    Результатом выполнения данного кода будет таблица истинности для конъюнкции трех условий:
    
    Как можно видеть из таблицы, значение конъюнкции трех условий будет равно 1 (True) только в том случае, когда все три условия истинны. В остальных случаях, значение выражения будет равно 0 (False).
    
    Решение основано на принципах работы с булевыми значениями (True/False) и логическими операциями (and). При помощи циклов for и операторов range мы перебираем все возможные комбинации значений переменных a, b и c, и для каждой комбинации вычисляем значение выражения a ∧ b ∧ c. Результаты вычислений выводим в таблицу истинности с помощью команды print() .
    
    Построение таблицы истинности для импликации в Python
    
    Как обозначается импликация в Python?
    
    Как мы ранее узнали, импликация — это логическая операция, которая означает «если…, то…». В Python, импликацию можно реализовать двумя способами:
    1. Надежный, но длинный. Через предобразование: A → B == not A or B
    2. Быстрый но ненадежный. Можно напутать с приоритетами операций, когда есть скобки. A → B == A<=B
    Давайте построим таблицу истинности для импликации с помощью Python:
    
    Здесь мы определяем функцию implication , которая принимает два аргумента a и b и возвращает значение импликации a -> b . Затем мы выводим заголовок таблицы истинности и используем два вложенных цикла `for`, чтобы перебрать все возможные комбинации значений a и b . Для каждой комбинации мы вычисляем результат функции `implication` и выводим значения a , b и результат в виде строки таблицы.
    
    Результат выполнения программы будет следующим:
    
    Здесь 1 означает True , а 0 — False . Как видим, значение импликации a -> b истинно только в тех случаях, когда a ложно или a и b истинны одновременно.
    
    Решение заданий ЕГЭ с помощью Python
    
    Логическая функция F задаётся выражением (x ≡ z ) ∨ (x → (y ∧ z)).
    
    Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F.
    
    Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z.
    
    Переменная 1 Переменная 2 Переменная 3 Функция
    
    . . . F
    
    0 0 0
    
    1 0
    
    В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
    
    Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:
    
    Переменная 1 Переменная 2 Функция
    
    . . F
    
    0 1 0
    
    Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.
    
    Для построения таблицы истинности данного логического выражения можно воспользоваться языком программирования Python и его возможностью работы с логическими операциями. Для этого можно написать следующий код:
    
    В данном коде мы задаем начальные значения переменных x, y и z как False. Затем мы выводим заголовок таблицы истинности и перебираем все возможные значения переменных x, y и z, используя вложенные циклы. Для каждой комбинации значений переменных мы вычисляем значение выражения и выводим результат в таблицу. В конце каждой строки таблицы мы переходим на новую строку с помощью команды print() .
    
    Результатом выполнения данного кода будет таблица истинности для данного логического выражения:
    
    Как можно видеть из таблицы, значение данного логического выражения будет равно 1 (True) только в тех случаях, когда x и z равны, или когда x равно True, а y и z также равны True. В остальных случаях, значение выражения будет равно 0 (False).
    
    Фильтруем таблицу истинности
    
    Для анализа таблицы, нам нужны только те значения итогового выражения, которые принимают значение 0 (False) , потому что в задании, для расшифровки, приведен фрагмент только с ложными значениями выражения.
    
    Для этого, внутри переборной конструкции из трех циклов for , сначала вычисляется значение логического выражения, а потом добавлено условие:
    
    В случае, если итоговое выражение (переменная result ), имеет ложное значение, мы печатаем фрагмент таблицы истинности.
    
    Сопоставляем получившийся фрагмент из программы и задания
    
    Шаг 1. Сравниваем две таблицы: получившуюся с помощью программы и фрагмента, данного в задании.
    
    Сравнивая две таблицы, мы видим только одну строку, где две исходных переменных одновременно равны 0 (False). Только значение переменной3 пусто. Значит, можно сделать вывод, что переменная3 — это x .
    
    Шаг 2. Оставшаяся строка фрагмента из задания, содержит только одно значение — 1 ( Переменная1 ).
    
    Ей соответствует нижняя строка результатов программы. Переменную x , мы исключаем, так как нашли ее на шаге 1. Значит — переменная 1 — это y , так как именно у нее значение 1 ( True ). Оставшаяся переменная 2 соответствует переменной z .
    
    Построение таблицы истинности с помощью Excel
    
    Для построения таблицы истинности в Excel мы можем использовать логические функции И ( AND ) и ИЛИ ( OR ). Давайте создадим новую таблицу в Excel и заполним ее значениями:
    
    A B
    
    0 0
    
    0 1
    
    1 0
    
    1 1
    
    Здесь столбцы A и B содержат все возможные комбинации значений True и False . Теперь мы можем добавить два новых столбца C и D, чтобы вычислить значения конъюнкции и дизъюнкции соответственно.
    
    Для конъюнкции мы можем использовать функцию И . В ячейку C2 введите формулу =И(A2;B2) и скопируйте эту формулу в ячейки C3:C5. Результаты вычислений должны быть такими:
    
    A B C
    
    0 0 0
    
    0 1 0
    
    1 0 0
    
    1 1 1
    
    Для дизъюнкции мы можем использовать функцию ИЛИ . В ячейку D2 введите формулу =ИЛИ(A2;B2) и скопируйте эту формулу в ячейки D3:D5. Результаты вычислений должны быть такими:
    
    A B C D
    
    0 0 0 0
    
    0 1 0 1
    
    1 0 0 1
    
    1 1 1 1
    
    Здесь мы видим, что результат дизъюнкции ИЛИ равен True только в тех случаях, когда хотя бы один из аргументов равен True . Результат конъюнкции И равен True только в том случае, когда оба аргумента равны True .
    
    Реализация импликации и тождества в Excel
    
    Для построения таблицы истинности для импликации в Excel мы можем использовать логическую функцию ЕСЛИ . Давайте создадим новую таблицу в Excel и заполним ее значениями:
    
    A B
    
    0 0
    
    0 1
    
    1 0
    
    1 1
    
    Здесь столбцы A и B содержат все возможные комбинации значений True и False . Теперь мы можем добавить новый столбец C, чтобы вычислить значения импликации.
    
    Для импликации мы можем использовать функцию ЕСЛИ , которая возвращает True , если условие истинно, и False , если условие ложно. В ячейку C2 введите формулу =ЕСЛИ(A2=1;B2;1) , где ; используется вместо запятой в русской локали Excel. Скопируйте эту формулу в ячейки C3:C5. Результаты вычислений должны быть такими:
    
    A B C
    
    0 0 1
    
    0 1 1
    
    1 0 0
    
    1 1 1
    
    Здесь мы видим, что результат импликации равен True только в тех случаях, когда логическое условие А истинно и логическое условие B также истинно, или когда логическое условие А ложно. Для выражения «A → B» это означает, что если A истинно, то B также должно быть истинно, но если A ложно, то B может быть истинно или ложно.
    
    Для реализации тождества с помощью Excel, можно использовать формулу: =ЕСЛИ(A2=B2;1;0) .
    
    Решение задания 2 ЕГЭ с помощью Excel
    
    Логическая функция F задаётся выражением (x ≡ y ) ∨ ((y ∨ z) → x).
    
    Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F.
    
    Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z.
    
    Переменная 1 Переменная 2 Переменная 3 Функция
    
    . . . F
    
    1 1 0
    
    1 0
    
    В ответе напишите буквы x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
    
    Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:
    
    Переменная 1 Переменная 1 Функция
    
    . . F
    
    0 1 0
    
    Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.
    
    Для построения таблицы истинности в Excel нам нужно создать столбцы для каждой переменной и один столбец для всего выражения. Затем мы используем функции Excel для вычисления значений выражения для всех возможных комбинаций значений переменных.
    1. Создайте столбцы для переменных x, y и z.
    2. Добавьте еще один столбец, который будет содержать выражение (x ≡ y ) ∨ ((y ∨ z) → x).
    3. В первой строке столбцов переменных напишите заголовки «x», «y» и «z».
    4. Заполните каждый столбец переменной всеми возможными комбинациями значений 0 и 1. Например, для двух переменных (x и y) у нас будет 4 строки: 1 и 1, 1 и 0, 0 и 1, и 0 и 0.
    5. Для столбца, содержащего выражение, используйте следующую формулу для первой строки и скопируйте ее для всех остальных строк:
    После того, как вы скопировали формулу для всех строк, вы должны увидеть таблицу, которая выглядит примерно так:
    
    Здесь мы видим результат вычисления выражения для каждой возможной комбинации значений переменных.
    
    Затем, мы должны отфильтровать результат и вывести только ложные значения выражения.
    
    И сопоставляем с фрагментом задания
    
    Переменная 1 Переменная 2 Переменная 3 Функция
    
    . . . F
    
    1 1 0
    
    1 0
    
    Мы видим, что у Переменной 3 оба значения равны ИСТИНА . Это соответствует переменной y .
    
    Переменная x у нас всегда принимает ложные значения. Значит Переменная 2 точно не x . Переменная 2 — это z .
    
    Как заменить следование в информатике
    
    Логические операции. ➞ Что такое конъюнкция, дизъюнкция, импликация
    
    Тот, кто хочет подробно разбираться в цифровых технологиях должен понимать основы такой темы, как алгебра логики. В этой статье будут разобраны основные определения, а также показаны самые важные логические операции, такие как конъюнкция, дизъюнкция, импликация и т.д.
    
    Основные положения
    
    Для начала следует разобраться, для чего нужна алгебра логики – главным образом, этот раздел математики и информатики, нужен для работы с логическими выражениями и высказываниями.
    
    Логическим высказыванием называется утверждение (или запись), которое мы можем однозначно классифицировать, как истинное или ложное (1 или 0 в информатике).
    
    Примером таким высказываний будут являться:
    1. Сегодня светит солнце;
    2. 5 > 3;
    3. Химическая таблица элементов была разработана Д.И. Менделеевым.
    Отсюда можно сделать вывод, что в русском языке логическими высказываниями являются повествовательные предложения, однако далеко не все повествовательные предложения являются логическими высказываниями . Пример: химия скучный предмет. Здесь мы не можем однозначно установить ложно ли это выражение или истинно.
    
    Логические высказывания делятся на два типа — простые и сложные.
    - Простые высказывания состоят из одного утверждения, которые мы можем однозначно охарактеризовать, как истинные или ложные.
    - Сложные же состоят из нескольких таких утверждений, которые объединены с помощью логических операций (рассмотрены дальше).
    В алгебре логики, как простые, так и сложные высказываниями описываются булевыми выражениями.
    
    Булево выражение – это символическое (знаковое) описание высказывания.
    
    В таких выражениях простые высказывания выступают в роли переменных и обозначаются буквами латинского алфавита, а операции обозначаются при помощи специальных знаков . После выполнения всех операций и упрощения выражения мы получаем результат, на основании которого строится таблица истинности.
    
    Операции
    
    Ниже рассмотрим основные операции, которые применяются в булевой алгебре. Их хватит, чтобы упростить львиную долю всех выражений, которые Вам встретятся.
    
    Конъюнкция
    
    Конъюнкция (булево умножение) — функция, по своему смыслу приближенная к союзу «И». При выполнении конъюнкции результат истинен (равен 1) тогда и только тогда, когда истинны ВСЕ переменные. Если хотя бы одно из высказываний ложно, то ложно и всё выражение (равно 0).
    
    Функция может работать как с двумя операндами (высказываниями), так и с тремя, четырьмя и т.д. В математике обозначается с помощью знаков $ \wedge $ и &. Обозначение в языках программирования AND, &&. Таблица истинности для двух операндов:
    
    Дизъюнкция
    
    Дизъюнкцией называется функция булева сложения. По смыслу дизъюнкция приближена к союзу «ИЛИ». В результате выполнения данной функции результирующие выражение является истинным, когда хотя бы одно из высказываний в этом выражении тоже истинно.
    
    Булево сложение, также как и умножение, может работать с произвольным количеством операндов. В математике обозначается как V, а в программировании с помощью OR или I.
    
    Инверсия
    
    Логическое отрицание – функция, работающая с одним высказыванием, и заменяющая истину на ложь, а ложь на истину. В математике обозначается с помощью черты над значением, а в программирование и информатике с помощью слова NOT.
    
    Импликация
    
    Также называется булевым следованием. В русском языке данной функции соответствует оборот «Если …, то …». Например, если на улице гремит гром, то стоит пасмурная погода.
    
    Результирующее значение будет ложным только тогда, когда из истинного высказывания будет следовать ложное следствие . Имеет обозначение в виде стрелочки $ \Longrightarrow $ . Важно: импликация работает только с двумя операндами.
    
    Эквивалентность
    
    Булева тождественность или равенство. На простом языке будет обозначено как «… эквивалентно (равно) …». Результат будет истинным тогда, когда все значения в выражении будут иметь одинаковую истинность.
    
    Обозначается с помощью трех черточек или ⟺.
    
    Порядок выполнения операций
    
    Логические операции выполняются в следующем порядке:
    1. Первой выполняется инверсия переменных.
    2. Вторым выполняется конъюнкция (булево умножение);
    3. Третьим номером идет дизъюнкция (сложение);
    4. Затем выполняется импликация;
    5. Самым низким приоритетом выполнения обладает эквивалентность.
    Если в формуле указаны скобки, то порядок выполнения действий в скобках точно такой же, как написано выше.
    
    Пример
    
    Дано два отрезка B = [2,10], C = [6,14]. Из предложенных вариантов ответа выберите такой отрезок A, что формула $ ((z \in A) \Longrightarrow (z \in B)) \vee (z \in C) $ истинна при любом значении z. Варианты ответа:
    1. [0,3];
    2. [3,11];
    3. [11,15];
    4. [15,17].
    Решение: Подставим в уравнение $ ((z \in A) \Longrightarrow (z \in B)) \vee (z \in C) $ =1 значения B и C и составим таблицу истинности:
    
    Получившаяся формула $ ((z \in A) \Longrightarrow (z \in [2,10])) \vee (z \in [6,14])=1 $. По условию $ z \in A $=1.
    
    Таблица истинности для всех отрезков:
    
    Ответ: A = [3,11].
    
    Видео
    
    Заключение
    
    Вот Вы и познакомились с основными логическими операциями и понятиями и знаете, что такое булево сложение и умножение. Если вас заинтересовала данная тема, то можете изучить булевы законы. Эти законы не проходятся в рамках школьной программы и служат для упрощения сложных выражений.
    
    Основные логические операции
    
    Логические операции в создании компьютерных программ — действия, которые производятся над входными данными. Такие функции производятся над сигналами булевского типа, то есть над примитивными выражениями, имеющими только два возможных значения: истина или ложь.
    
    Виды операций
    
    В программировании выделяют следующие виды функций:
    1. Логическое умножение или конъюнкция.
    2. Логическое сложение или дизъюнкция.
    3. Логическое отрицание или инверсия.
    4. Логическое следование или импликация.
    5. Логическая равнозначность или эквивалентность.
    6. Стрелка Пирса.
    7. Штрих Шеффера .
    Логическое умножение (конъюнкция)
    
    Конъюнкция — это действие, в результате которого каждым двум входным данным соответствует одно новое высказывание. Истинное значение на выходе получается, когда оба входных значения истинны.
    
    Осторожно! Если преподаватель обнаружит плагиат в работе, не избежать крупных проблем (вплоть до отчисления). Если нет возможности написать самому, закажите тут.
    
    Для обозначения логического умножения используют союз «и», значки $ \wedge$ , $\&.$
    
    Таблица истинности для логического умножения выглядит так:
    
    A, B — исходные данные;
    
    A и B — значение, приобретаемое в результате реализации конъюнкции.
    
    Из таблицы следуют свойства логического умножения:
    - при ложном значении одной входной информации из двух конъюнкция будет ложной;
    - при истинном значении переменных конъюнкция будет истинной;
    - результат логического умножения не зависит от порядка записи ее переменных.
    Логическое сложение (дизъюнкция)
    
    Дизъюнкция — это булева функция, в итоге которой выходные данные будут ложными только при ложности всех исходных выражений.
    
    Обозначается дизъюнкция союзом «или», символами +, $ \vee$ .
    
    Таблица истинности логического сложения:
    
    A, B — входная информация;
    
    A или B — значение, приобретаемое в результате выполнения дизъюнкции.
    
    Для дизъюнкции справедливы следующие утверждения:
    - при истинности хотя бы одного подвыражения дизъюнкция будет истинной;
    - при ложности всех высказываний дизъюнкция примет ложное значение;
    - итог дизъюнкции не зависит от перемены мест слагаемых.
    Логическое отрицание (инверсия)
    
    Инверсия — выражение, ставящее в соответствие одному значению противоположное.
    
    Условное обозначение логического отрицания: с помощью частицы «не», символов ¯, $\neg.$
    
    Таблица истинности инверсии:
    
    A — исходные данные;
    
    не A — значение, приобретаемое в результате логического отрицания.
    
    Логическое следование (импликация)
    
    Импликация — это булева операция, ложная лишь тогда, когда первая исходная переменная является истиной, а вторая — ложью.
    
    Следование записывается с помощью знака $\rightarrow.$
    
    Таблица истинности для импликации:
    
    A — входная информация, означающая условие;
    
    B — входная информация, означающая следствие;
    
    A → B — значение, приобретаемое в результате импликации.
    
    По своему употреблению данная связка схожа со значением союзов «если. то. ».
    
    Логическая равнозначность (эквивалентность)
    
    Эквивалентность — выражение, являющееся истинным лишь в случае равенства двух входных элементов.
    
    При записи равнозначности используют стрелки $\Leftrightarrow$ , $\leftrightarrow$ , $\Xi$ .
    
    Таблица истинности для равнозначности:
    
    Стрелка Пирса
    
    Стрелка Пирса — двухместное логическое действие со следующей последовательностью: сначала над исходными показаниями производится дизъюнкция, затем происходит отрицание полученного результата.
    
    Данная манипуляция является отрицание логического сложения. Свое название рассматриваемая функция получила от своего автора — американского ученого Чарльза Пирса.
    
    Запись стрелки Пирса осуществляется через знак $\downarrow$ .
    
    Таблица истинности для этой операции следующая:
    
    Особенность стрелки Пирса заключается в ее возможности строить другие булевы функции.
    
    Пример
    
    Штрих Шеффера
    
    Штрих Шеффера — это действие, приводящее к ложному итогу лишь при истинности обоих исходных данных. По порядку выполнения операций эта функция эквивалентна отрицанию конъюнкции.
    
    Символ Шеффера назван по фамилии своего создателя — американского логика Генри Шеффера — и обозначается посредством знака $\vert.$
    
    Таблица истинности для данной функции:
    
    С помощью штриха Шеффера можно воспроизвести другие логические манипуляции.
    
    Пример
    
    Порядок выполнения операций
    
    В составном логическом выражении действия выполняются в такой последовательности:
    - инверсия;
    - конъюнкция;
    - дизъюнкция;
    - импликация;
    - эквивалентность.
    Для построения нужного порядка, как и в математических выражениях, используют скобки.
    
    Логические операции
    
    Универсальный подход помогает решать разнотипные задачи, даже не вникая в условие детально. Именно для этого нужны логические задачи и универсальные способы решения. Существует множество подходов, но наиболее распространены 3 основных:
    - Способ рассуждений.
    - Табличный способ.
    - Решение при помощи средств логики.
    Первый позволяет находить правильный ответ, обдумывая каждый пункт задачи, делая выводы из каждого условия. Этим методом мы пользуемся постоянно, в обычной жизни, решая простые бытовые примеры. Он простой, но для сложных задач не подходит.
    
    Табличный метод сокращает форму записи примера и позволяет перебрать все возможные значения исходных данных, анализируя результат, полученный при каждой комбинации. Это очень наглядно, компактно и позволяет использовать обычные слова или же логические обозначения.
    
    Поиск правильного решения средствами логики выводит решение примеров на новый уровень, позволяя абстрагироваться от лишней информации, выделяя только переменные, их взаимосвязи. Это позволяет решать задачи из любой сферы, не вникая в те данные, которые не важны для самого решения. Логическая основа задачи – своеобразный «скелет», а вся сопутствующая информация – «одежда».
    
    Алгебра логики и решение задач
    
    Несмотря на то, что логика, как наука о размышлении, существовала еще 5 в. До н.э., теперь это важная часть многих наук, а не только философии и риторики. Также логика существует, как отдельная наука уже более 200 лет.
    
    Инструменты алгебры логики позволяют переводить словесные высказывания в сухие, объективные выражения, а с их помощью выполнять различные логические операции.Появился этот раздел математики 200 лет назад.
    
    Стоит остановиться на базовых понятиях алгебры логики:
    - константы (0,1);
    - переменные;
    - формула;
    - знаки операций;
    - скобки.
    Логическая переменная – обозначение логического выражения, которое может быть true (t, правда, истина, да, 1) – false (f, ложь, нет, 0).
    
    Формула– символьный способ выражения операции между переменными при помощи специальных знаков и скобок ().
    
    Логическое высказывание – утверждение, в котором говорится только правда или только ложь.
    
    Образец таких предложений: «Луна – вертится вокруг Марса» – ложно, а «После зимы всегда приходит весна» – истинно.
    
    Частицы «не», «или», если», «и» и другие, которые являются связующими элементами в обычной речи, позволяют создавать элементарные логические выражения.
    
    Элементарные высказывания – те, к которым нельзя применить понятие истинности или ложности. Их обозначают различными символами (латинские буквы, цифры), знаками. Ими занимаются те сферы, к которым они относятся. Они входят в состав высказываний логики.
    
    Из одних высказываний можно образовывать другие, в результате получая составные высказывания. И от того, являются исходные элементы составного конечного высказывания правдивыми или неправдивыми, а также какие логические связки использовались, будет правдой или ложью все высказывание в целом.
    
    Чтобы образовать такое составное предложение в обычной жизни, используют связки И, ИЛИ, НЕ. А научный подход заменил их на конъюнкцию, дизъюнкцию, инверсию и более сложные операции. Все эти процессы выражают словесно, таблично (таблицы истинности) или графически (диаграммы Эйлера-Венна).
    
    Простые выражения содержат лишь одно выражение (правдивое или нет), и не содержит никаких логических операций.
    
    Сложные могут содержать от 2 и больше аргументов (простых выражений), которые между собой связаны логическими операциями.
    
    Еще используют понятие «предикат» – содержит любое количество переменных без перечисления всех составляющих данных. Это предикат простых, отрицательных P(x)=(x<0) чисел.
    
    Чтобы исключить лишнюю информацию, оставив только логические связи, используют таблицы истинности, наглядно демонстрирующие, правдиво или неправдиво конечное предложение, если учесть все значения входящих в его состав простейших частей.
    
    Такая форма оформления и решения задач используется в построении электросхем, для решения различных логических задач, в булевой алгебре, программировании.
    
    Основные операции
    
    Количество логических операций, которыми обычно оперирует логика 6:
    - Отрицание.
    - Умножение.
    - Сложение
    - Следование.
    - Дизъюнкция.
    - Равнозначность.
    Остановимся на каждом из них детальнее, выясним как правильно они называются в алгебре логики, есть ли у них аналоги в обычной речи, в математике, и как их можно использовать в обычной жизни.
    
    Отрицание или инверсия
    
    Операция отрицания или НЕлогическое, корректнее будет название инверсия.Конечное высказывание будет противоположным первоначальному (исходному). Применяется для одного выражения, которое может быть как сложным, так и элементарным.
    
    На примере этой простейшей операции удобно показывать, насколько лаконичны и информативны таблицы истинности. Обозначим исходное высказывание буквой А, соответственно, окончательное будет не А (или НЕ, ‾, ˥ not А). А их ложность или правдивость напишем при помощи цифр 0 и 1.
    
    Получается, если исходное значение правда, то новое будет ложь, и наоборот.
    
    Умножение или конъюнкция &
    
    Логическое И или умножение еще называют конъюнкцией. Финальное высказывание будет правдивым, только если его составляющие тоже правдивы. Во всех остальных случаях оно будет ложным. Применяется для двух и более аргументов, элементарных или сложных. Обозначение А и В; А ^ В; А &В; A and В.
    
    Как видно, при помощи таблицы истинности из 15 ячеек можно описать то, на описание чего при помощи слов пришлось бы потратить минимум 5 полноценных предложений.
    
    Логическое И в обычной жизни:
    - Хорошая певица должна быть талантливой и упорной (наличие только одного качества не позволит проявить миру свой талант).
    - По условиям задачи А – число меньше 30, В – число делиться на 3. Нужно найти решение А ˄ В.
    Решение: Первое множество содержит числа 1,2,3….29. Второе – 3,6,9,…27. Решением будет множество на пересечении множеств А и В, что хорошо покажут диаграммы Эйлера-Венна. А ˄ В будет истинным для множества чисел 3,6,9,….27.
    
    Сложение или дизъюнкция V
    
    Логическое ИЛИ, сложение по-другому называют дизъюнкцией. Оно истинно всегда, кроме случая, если ложны все составные высказывания. Функция распространяется на простые и сложные исходные аргументы. Обозначение А или В; A v В; А ог В.
    
    В обычной жизни нас окружает логическое ИЛИ:
    - «Чтобы сдать тесты на «отлично», нужно старательно готовиться ИЛИ должно повезти с билетом».
    - Есть задача с 2-мя условиями: А – число делится на 5, В – число делится на 2.
    Решение: Первое множество чисел включает в себя 5, 10, 15…Второе – 10, 20, 30…Решение, при котором истинно Аv В – совокупность обеих множеств (5, 10, 15, 20, 25, 30…).
    
    Следование или импликация
    
    Для этого случая важно значение каждого выражения и даже его очередность, потому что первый аргумент считается условием, второй – следствием. Импликация будет ложной лишь в одном случае – если первое составляющее правдиво, а второе нет.
    
    Такое логическое следование имеет аналог в обычной речи «если.. то», то есть одно событие зависит от другого. Символьно связи выражают следующим образом:
    
    Логическое следование в обычной жизни:
    - Если пойти к врачу, можно выздороветь (но можно выздороветь и без похода к врачу, а можно и после визита в больницу не выздороветь).
    - По условию задачи, А – если число делится на 10, то В делится на 5.
    Строгая дизъюнкция
    
    Такая логическая операция выдаст истину, если любое из составляющих высказываний будет истинным, независимо очередности.
    
    Это пример исключающей функции. Аналог в словесном выражении – «либо». Разница от простой дизъюнкции в том, что конечное выражение будет истинным, только если будет правдой одна переменная.
    
    Эквиваленция или равнозначность
    
    Операция, выдающая истину в случае, если обе исходные переменные истины или неправдивы.Обозначают А
    
    В, А ↔ В.
    
    Словесная аналогия – «тогда и только тогда, когда», математическая – «необходимо и достаточно». Если сравнить таблицы истинности для предыдущих операций, очевидно, что она противоположна «исключающему ИЛИ», то ее можно посчитать так:
    
    Пример эквивалентности из обычной жизни:
    - Если вечером на горизонте солнце темно-красного цвета, значит, завтра будет ветреный день.
    - В задаче 2 условия: А – сумма цифр числа равно 9, В – число делится на 9. АВ означает, что число делится на 9, если сумма цифр равна 9.
    Сравнение операций, первоочередность
    
    Приведены результаты основных логических функций для 2-х переменных:
    
    Если выражение громоздкое, состоящее из нескольких основных, анализ выполняют по приоритетности функций, по очереди написания, от начала:
    
    Но скобки делают операцию внутри них самой приоритетной.
    
    Законы алгебры логики
    
    Операции логики подчиняются законам, которые во многом напоминают математические законы. Другими словами, операции обладают определенными свойствами, которые упрощают решение и позволяют преобразовывать одни операции в другие.
    
    Таблица законов алгебры логики
    
    Диаграммы Эйлера-Венна
    
    Тем, кто лучше воспринимает информацию в виде изображений, понравятся диаграммы Эйлера-Венна, которые показывают, как пересекаются множества между собой.
    
    Число пересечений (областей) можно посчитать сразу, оно равно n = 2 N , где N – число множеств. Так как значение двойки в степени растет очень быстро (4,8,16), обычно диаграммы используют для 2-3 множеств. Далее области пересечения будут сливаться, образуя неразличимые участки. Если множеств 2-3, то рисуют круги, если больше 4 – эллипсы. Этот «цветок» помещают в прямоугольную конструкцию, которую называют универсум U (универсальное множество).
    
    Диаграммы позволяют наглядно увидеть результат большинства логических функций:
    
    Конъюнкция множеств А и В:
    
    Сложное выражение (Ā)∨(A∧B), составленное из элементарных Ā, A∧B и их комбинации, графическое выражение:
    
    Примеры использования диаграмм Эйлера-Венна
    
    Есть 2 множества цифр и универсум:
    
    Пустой области ничего не принадлежит, опишем в табличном виде, какие цифры какой области принадлежит:
    
    Электросхемы и таблицы истинности
    
    При помощи «0» и «1» можно обозначить, светится ли лампочка, идет ли ток при параллельном или последовательном соединении проводов. Это настолько удобно, что у разных логических функций есть стандартные обозначения при построении электрических схем:
    
    Переменными являются переключатели, а результат (горит лампа/идет ток) будет «1» – истина или «0» – ложь.
    
    Для конъюнкции и инверсии подходит последовательное соединение, но во втором случае переключатель один, для дизъюнкции – параллельное.
    
    Это примеры простейших электросхем. Понимание простейших логических взаимосвязей, умение быстро строить и анализировать электроцепи позволяет строить, паять более сложные, многоуровневые схемы. Для автоматизации применяют различные программы, самый простой вариант – таблицы Excel.
    
    Импликация
    
    Импликация или логическое следование соответствует обороту «если. то. », обозначается A→ B. Таблица истинности импликации имеет вид:
    
    Высказывание A→ B ложно в том и только в том случае, когда условие (первое высказывание A) истинно, а следствие (второе высказывание B) ложно.
    
    A = «Завтра будет хорошая погода»
    
    В = «Я пойду гулять»
    
    A→ B = «Если завтра будет хорошая погода, я пойду гулять»
    
    Другой пример сложного высказывания: «Если поезд прибывает на данный путь, то подается сигнал, что путь закрыт».
    
    A= « Поезд прибывает на данный путь»
    
    В= «Подается сигнал, что путь закрыт»
    
    Рассматриваемое сложное высказывание истинно, если:
    
    1) поезд прибывает, сигнал «закрыт» (1, 1, 1);
    
    2) поезд не прибывает, сигнал «свободен» (0, 0, 1);
    
    3) поезд не пребывает, сигнал «закрыт» (0, 0, 1) — если поезд не пребывает, безопасен любой сигнал.
    
    Высказывание ложно (безопасность не обеспечивается) только в том случае, если поезд прибывает, а сигнал «свободен» (1, 0, 0).
    
    Операция импликации в русском языке является самой «загадочной». Ей соответствую также следующие речевые обороты: «из А следует В»; «В только в случае А»; «А влечет В»; «А достаточно для В»; «В необходимо для А».
    
    В обычной речи связка «если . то…» описывает причинно-следственную связь между высказываниями. Но в логических операциях смысл высказываний не учитывается. Рассматривается только их истинность или ложность. Поэтому не надо смущаться «бессмысленностью» импликаций, образованных высказываниями, совершенно не связанными по содержанию. Например, такими: «если президент США — демократ, то в Африке водятся жирафы», «если арбуз — ягода, то в бензоколонке есть бензин».
    
    Эквивалентность
    
    Эквивалентность (равноценность или равнозначность) соответствует оборотам речи «тогда и только тогда», «в том и только в том случае», «. равносильно . » и обозначается A↔B , или A≡B.
    
    Таблица истинности эквивалентности имеет вид:
    
    Выражение A↔B истинно в том и только в том случае, когда оба исходных высказывания одновременно истинны или одновременно ложны.
    
    Пример эквивалентности: «Петя выучит уроки тогда и только тогда, когда Пете поставят хорошую отметку».
    
    В русском языке операции эквивалентности также соответствует речевой оборот «A необходимо и достаточно B».
    
    Строгая дизъюнкция
    
    Строгая дизъюнкция или «исключающее или», соответствует оборотам речи «или. или. » или «либо. либо...», и обозначается AB .
    
    Таблица истинности эквивалентности имеет вид:
    
    Выражение AB истинно в том и только в том случае, когда исходные высказывания A и B не равны между собой.
    
    Это определение можно обобщить для любого количества логических переменных, объединенных строгой дизъюнкцией. Например,
    
    A B C = 1, (3)
    
    только если одно из трёх высказываний A, B, C истинно.
    
    Логические формулы и функции Логическая формула
    
    С помощью логических переменных и символов логических операций любое сложное (составное) высказывание можно записать в виде логической формулы. Её определение:
    
    Всякая логическая переменная и символы «истина» («1») и «ложь» («0») — формулы.
    
    Если А и В — формулы, то — тоже формулы.
    
    Никаких других формул в алгебре высказываний нет.
    
    Значение логической формулы определяется заданными значениями входящих в формулу переменных. Тем самым каждая формула может рассматриваться как способ задания функции в алгебре высказываний.
    Похожие публикации: