Центр подготовки к ЕГЭ > Материалы для подготовки к ЕГЭ и ОГЭ > Программа ЕГЭ по информатике — Разбор задач и материалы > Актуальные видео по информатике > Алгебра логики: Конъюнкция, Дизъюнкция, Импликация, Эквивалентность

Алгебра логики: Конъюнкция, Дизъюнкция, Импликация, Эквивалентность

Лада Есакова, преподаватель информатики и математики, автор книги "Информатика. Полный курс подготовки к ЕГЭ".

Ну а теперь, ребята, самая «вкусная» тема теоретической части ЕГЭ – это булева алгебра, она же алгебра логики.

Сначала я хочу задать вам вопрос: для чего вообще придумали такой аппарат как булева алгебра, кроме того, чтобы мучить маленьких детей?

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

А кто такой компьютер? Если очень упрощенно, то это некоторое устройство, у которого на проводники подается либо не подается ток. Так вот в зависимости от того, есть ток или его нет на входящих проводниках, происходят определенные действия. Обозначим это 0 и 1: 0 – нет тока, 1 – есть ток. Вот именно в таких терминах нам и надо разговаривать с компьютером.

Рассматривая задачи, в том числе и 27, сложную задачу, считаем, что мы крутые программисты, если мы написали программный код на каком-то языке программирования. А компьютер нас поймет? Нет. Он знает только 0 и 1. Как же нам тогда до него достучаться?

После программистов высокого уровня в дело вступают Боги от программирования – это люди, которые пишут компиляторы, драйверы, операционные системы и которые уже непосредственно пытаются достучаться до компьютерного железа.

Что такое уже перевод программы в машинные коды? У меня нет цели рассказать, как это работает детально, я расскажу очень упрощенно, чтобы просто было понятно, для чего это нужно.

Если на один компьютерный разъем ток не поступил, а на другой поступил, мне нужно, чтобы получился 0. Я уже говорю терминами 0 и 1, нет тока или есть ток.

Если на оба разъема ток не поступил, тоже будет 0.

Если наоборот на первый поступил, а на второй не поступил, – то я тоже хочу 0. И в случае, если на оба разъема ток поступил, тогда пусть будет у меня 1

Например, у меня другая схема, в которую входит три проводника, и, в зависимости от того, что пришло на входы, я тоже хочу какое-то значение. Например, вот так. Не буду расписывать все варианты

По сути, у меня единственный возможный способ общаться с компьютером – это завести много функций от разного числа переменных, которые могут быть только 0 и 1 и которые на выходе дают тоже 0 или 1.

Можно посмотреть функцию от двух переменных и назвать ее f(1), функцию от трех переменных назовем f(2). Будут и другие функции, которые запишем в таблицы, переплету в многотомники и поставлю на полку. В случае, если мне нужно найти какую-то схему, достаю том, листаю страницы и нахожу то, что мне нужно.

Для компьютера это будет нормально, его устроит, если я выстрою с ним такой диалог. А вот человека такая схема работы не устроит, потому что людям очень сложно оперировать большими объемами информации без логического обоснования. Нам проще понять, как это работает, чем зубрить большое количество таблиц. Поэтому человек для облегчения своей жизни ввел аналогию – истину и ложь.

Наверняка вы помните детсадовские игры, когда можно задавать только вопросы, на которые можно ответить «да» или «нет», и нужно что-то угадать. Наверное, у детей изначально подсознательно заложена склонность к двоичному коду.

Поэтому человек поставил в соответствие аппарат логических высказываний, и теперь за 0 мы принимаем ложь, за 1 – истину. И выяснилось, что если я такими операциями буду оперировать, то все операции от трех, четырех, пяти и т. д. переменных я могу свести к функциям от двух переменных. А к каким же функциям?

Первая функция – это функция отрицания. Ее можно обозначить несколькими способами - $HEa,\rightharpoondown a,\bar{a}$ .

Посмотрим, как это работает.

Если у меня высказывание ложное (например, я показываю маркер, а говорю, что это апельсин)

$a$	$\bar{a}$
0
1

А если я показываю маркер и говорю, что это не апельсин, то это истина

$a$	$\bar{a}$
0	1
1

Если я наоборот говорю, что это маркер и показываю его, то это истина, а если я говорю, что это не маркер, это будет ложь

$a$	$\bar{a}$
0	1
1	0

Следующая операция – это логическое ИЛИ, она же записывается как $\vee, \setminus, \dotplus$ .

Покажу как это работает.

Функция от двух переменных работает следующим образом: например, я говорю, что это апельсин или это яблоко (то есть два ложных высказывания), в сумме получается 0; если я говорю, что это апельсин или это маркер, в целом я сказала правду, потому что одно из утверждений является истинным, то получается 1; если я говорю, что это маркер или это банан, опять же это правда; и наконец, если я говорю, что это маркер или это маркер, то есть два верных утверждения, это тоже правда

$a b$	$a\setminus b$
00	0
01	1
10	1
11	1

Вот таким образом работает функция. Акцентирую ваше внимание, что мне ненужно запоминать эти наборы. Конечно, они запомнятся после несколько десятков прорешанных задач, но эту таблицу истинности не надо запоминать, это вытекает из логики.

Далее логическое И - $\wedge$ , &, знак умножения.

Посмотрим, как оно работает. Если я говорю два ложных утверждения – это яблоко и это банан – это ложь. Если я говорю, что это яблоко и это маркер – одно высказывание истина, но я же настаиваю на том, что и то, и другое должно выполняться, поэтому это ложь. Если я говорю, что это маркер и это банан, то это тоже ложь. И если я говорю два истинных утверждения – это маркер и это маркер – да, это правда

$a b$	$a\wedge b$
00	0
01	0
10	0
11	1

А умножение, потому что если 1 умножить на 0 или 0 на 1, то тоже будет 0, и только в случае умножения 1 на 1 получится 1.

Вот именно к этим операциям можно свести и все остальные, но не всегда удобно, поэтому еще две функции используется в курсе школьной программы – это импликация и эквивалентность.

Импликацию можно свести к вышеперечисленным, но удобнее ее использовать по-другому.

Импликация – это логическое следование $a\rightarrow b$

Не будем зубрить таблицу истинности, а попробуем понять.

Если у меня есть ложное высказывание (например, 2 больше 5), могу ли я получить из него ложь разрешенными функциями? Легко! Добавлю к двум частям неравенства единицу и получу ложь: 2>5, 3>6.

То есть мы можем получить изо лжи ложь.
А могу ли я изо лживого высказывания получить истину? Тоже могу. -5 больше -3. Это ложь? Ложь. А применим-ка разрешенную операцию – возведение в квадрат. И запросто получим истину: -5>-3, 25>9. То есть изо лжи истину мы тоже можем получить.

А вот из истины получить ложь никак не получится. Из истины можно получить только истину.
Ну и из истины истину получить, конечно же, возможно.

$a b$	$a\rightarrow b$
00	1
01	1
10	0
11	1

То есть не всегда удобно приводить импликацию к другим функциям. Потому что это замечательная функция, которая 0 дает в единственном случае, когда из истины следует ложь.
И последняя функция, часто употребляемая, – это функция эквивалентности, обозначается логическим равенством $\equiv$ или взаимными стрелками $\leftrightarrow$

Здесь все очень просто. 0 равен 0? Да. 0 = 1? Нет. 1 равна 0? Нет. 1 равна 1? Да.

$a b$	$\equiv$
00	1
01	0
10	0
11	1

Мы логически обосновали все пять функций, и это избавляет нас от необходимости зубрить таблицы истинности. Да, мы их запомним в процессе решения задач, но гораздо проще логически понять, в чем суть вопроса.

Теперь приоритеты этих функций.

Если у нас не стоят никакие скобки, то все действия, как и в математике, имеют некоторый приоритет.

Вот такая cтрока без скобок $\rightharpoondown a\vee b\wedge c\equiv d\rightarrow f$

Первый приоритет имеет отрицание $\rightharpoondown$ , оно прямо приклеивается к тому высказыванию, рядом с которым стоит $(\rightharpoondown a)$ , поэтому я всегда настаиваю использовать вот такой символ, черточку сверху $\bar{a}$ , потому что это гораздо понятнее, что оно относится к высказыванию.

Следующий приоритет – умножение $\wedge$ . То есть в нашем выражении у нас будет вот так $(\bar{a}) \vee (b\wedge c)\equiv d\rightarrow f$

Третий приоритет у сложения $\vee$ , То есть вот так $((\bar{a})\vee (b\wedge c))\equiv d\rightarrow f$ .

А дальше одинаковый приоритет имеют эквивалентность и импликация $\equiv, \rightarrow$ , слева на право. В нашем случае сначала выполнится сравнение на эквивалентность, а потом из этого импликация $(((\bar{a})\vee (b\wedge c))\equiv d)\rightarrow f$ .

Все видео по информатике

Спасибо за то, что пользуйтесь нашими материалами. Информация на странице «Алгебра логики: Конъюнкция, Дизъюнкция, Импликация, Эквивалентность» подготовлена нашими авторами специально, чтобы помочь вам в освоении предмета и подготовке к экзаменам. Чтобы успешно сдать необходимые и поступить в высшее учебное заведение или техникум нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий. Также вы можете воспользоваться другими материалами из данного раздела.

Публикация обновлена: 08.05.2023

Алгебра логики: Конъюнкция, Дизъюнкция, Импликация, Эквивалентность

Это полезно