Известно что импликация x y истина
Перейти к содержимому

Известно что импликация x y истина

  • автор:

Логические операции над высказываниями

Эта логическая операция соответствует в обыденной жизни частице «не».

Определение. Отрицанием высказывания x называется новое высказывание, которое является истинным, если высказывание ложно, и ложным, если высказывание x истинно.

Отрицание высказывания x обозначается и читается не x . Логические значения высказывания модно описать с помощью таблицы, которая называется таблицей истинности:

Пусть x высказывание. Так как тоже высказывание, то можно образовать отрицание высказывания , то есть высказывание , которое является двойным отрицанием высказывания x . Логические значения высказываний и x совпадают.

2. Дизъюнкция (логическое сложение).

Эта логическая операция соответствует союзу «или».

Определение. Дизъюнкцией двух высказываний x , y называется новое высказывание, которое считается истинным, если хотя бы одно из высказываний x или y истинно и ложным, если они оба ложны.

Дизъюнкция высказываний x , y обозначается x y и читается « x или y ». Логические значения дизъюнкции описываются таблицей истинности:

Высказывания x , y называются членами дизъюнкции.

x – «5>3», y «2>4». Тогда x y – «5>3» «2>4» истинно, так как истинно высказывание x .

В алгебре логики союз «или» всегда употребляется в неисключающем смысле. Из определения дизъюнкции и отрицания следует, что высказывание x всегда истинно.

Эта логическая операция соответствует союзу «и».

Определение. Конъюнкцией двух высказываний x , y называется новое высказывание, которое считается истинным, если оба высказывания x , y истинны, и ложным, если хотя бы одно из них ложно.

Конъюнкция высказываний x , y обозначается и читается « x и y ». Высказывания x , y называются членами конъюнкции. Логические значения конъюнкции описываются следующей таблицей истинности:

x – «6 делится на 2», y – «6 делится на 3». Тогда – «6 делится на 2» «6 делится на 3» истинно.

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

Из определения операций конъюнкции и отрицания следует, что высказывание всегда ложно.

Эта логическая операция соответствует словам «если …, то…».

Определение. Импликацией двух высказываний x , y называется новое высказывание, которое считается ложным, если x истинно, а y ложно, и истинным во всех остальных случаях.

Импликация высказываний обозначается x y и читается «если x , то y » или «из x следует y ». Высказывание x называется условием или посылкой, а высказывание yследствием или заключением. Высказывание x → y называется следованием или импликацией. Логические значения операции импликации описываются следующей таблицей истинности:

1) x – «12 делится на 6», y – «12 делится на 3». Тогда импликация x y – «если 12 делится на 6, то оно делится на 3» истинна, так как истинна посылка x , и истинно заключение y .

2) x – «12 делится на 2 и 3», y – «12 делится на 7». Тогда импликация x y – «если 12 делится на 2 и 3, то оно делится на 7» ложна, так как условие истинно, а заключение ложно.

Употребление слов «если …, то…» в алгебре логики отличается от употребления их в обыденной речи, когда, как правило, считается, что если высказывание x ложно, то высказывание «если x , то y » вообще не имеет смысла. Кроме того, строя предложение «если x , то y » в обыденной речи всегда подразумевается, что предложение y вытекает из предложения x . Употребление слов «если…, то…» в математической логике не требует этого, так как в ней смысл высказываний не рассматривается.

Импликация играет важную роль в математических доказательствах, так как многие теоремы формулируются в условной форме «если x , то y ». Если при этом известно, что x истинно и доказана истинность импликации x y то истинно и заключение y . В этом случае пишут x y и говорят, что из x следует y . Это классическое правило вывода постоянно используется в математике.

1. Эквиваленция .

Эта логическая операция соответствует словам «тогда и только тогда, когда».

Определение. Эквиваленцией или эквивалентностью двух высказываний x , y называется новое высказывание, которое считается истинным, если оба высказывания x , y либо одновременно истинны, либо одновременно ложны, и ложным во всех остальных случаях.

Эквиваленция высказываний x , y обозначается символом xy и читается «для того чтобы x , необходимо и достаточно, чтобы y » или « x тогда и только тогда, когда y ». Логические значения операции эквиваленции описываются следующей таблицей истинности :

Логические операции над высказываниями

Практически 100%-ая копия полюбившегося многим инстаграм, идеально подойдет для портфолио, презентации работ своим клиентам или как отклик на понравившуюся вакансию. Молодой ресурс, но администраторы оперативно реагируют на предложения и вопросы.

Логические операции над высказываниями

Существует 5 логических операций:

Обозначается $\bar < X >$, читается как «не $X$» или «неверно, что $X$». Логические значения высказывания $\bar < X >$ можно описать с помощью таблицы

$x$ $\bar < x >$
1 0
0 1

Таблицы такого вида принято называть таблицами истинности.

Конъюнкцией двух высказываний $X$, $Y$ называется высказывание, которое считается истинным, если оба высказывания $X$, $Y$ истинны, и ложным, если хотя бы одно из них ложно.

Конъюнкция высказываний $X$, $Y$ обозначается символом $X$&$Y$ или $X$$\wedge$$Y$ , читается «$X$ и $Y$». Высказывания $X$ и $Y$ называются членами конъюнкции или конъюнктивными элементами.

Логические значения конъюнкции описываются следующей таблицей истинности:

$x$ $y$ $x$&$y$
1 1 1
1 0 0
0 1 0
0 0 0

Дизъюнкцией двух высказываний $X$ и $Y$ называется высказывание, которое считается истинным, если хотя бы одно из высказываний $X$ и $Y$ истинно, и ложным, если они оба ложны.

Дизъюнкция высказываний $X$ и $Y$ обозначается символом $X$$\vee$$Y$, читается «$X$ или $Y$», где «или» используется в неразделительной форме. Высказывания $X$ и $Y$ называются членами дизъюнкции.

Логические значения дизъюнкции описываются следующей таблицей истинности:

$x$ $y$ $x\vee y$
1 1 1
1 0 1
0 1 1
0 0 0

Например, высказывание «В треугольнике $DFE$ угол $D$ или угол $E$ острый» истинно, так как обязательно истинно хотя бы одно из высказываний: «В треугольнике $DFE$ угол $D$ острый», «В треугольнике $DFE$ угол $E$ острый».

Импликацией двух высказываний $X$ и $Y$ называется высказывание, которое считается ложным, если $X$ истинно, а $Y$ — ложно, и истинным во всех остальных случаях.

Импликация высказываний $X$ и $Y$ обозначается символом $X \rightarrow Y$, читается «если $X$, то $Y$» или «из $X$ следует $Y$». Высказывание $X$ называют посылкой, высказывание $Y$ – заключением.

Логические значения операции импликации описываются следующей таблицей истинности:

$x$ $y$ $x\rightarrow y$
1 1 1
1 0 0
0 1 1
0 0 1

Например, высказывание «Если число 12 делится на 6, то оно делится на З», очевидно, истинно, так как здесь истинна посылка «Число 12 делится на 6» и истинно заключение «Число 12 делится на 3».

Употребление слов «если . то . » в алгебре логики отличается от употребления их в обыденной речи, где мы, как правило, считаем, что, если высказывание $X$ ложно, то высказывание «Если $X$, то $Y$» вообще не имеет смысла. Кроме того, строя предложение вида «если $X$, то $Y$» в обыденной речи, мы всегда подразумеваем, что предложение $Y$ вытекает из предложения $X$.

Употребление слов «если . то . » в математической логике не требует этого, поскольку в ней смысл высказываний не рассматривается.

Эквиваленцией < или эквивалентностью >двух высказываний $X$ и $Y$ называется высказывание, которое считается истинным, когда оба высказывания $X$, $Y$ либо одновременно истинны, либо одновременно ложны, и ложным во всех остальных случаях.

Эквиваленция высказываний $X$, $Y$ обозначается символом $X$$\leftrightarrow $$Y$, читается «для того, чтобы $X$, необходимо и достаточно, чтобы $Y$» или «$X$ тогда и только тогда, когда $Y$». Высказывания $X$, $Y$ называются членами эквиваленции.

Логические значения операции эквиваленции описываются следующей таблицей истинности:

$x$ $y$ $x\leftrightarrow y$
1 1 1
1 0 0
0 1 0
0 0 1

Например, эквиваленция «Треугольник $SPQ$ с вершиной $S$ и основанием $PQ$ равнобедренный тогда и только тогда, когда $\angle P = \angle Q$» является истинной, так как высказывания «Треугольник $SPQ$ с вершиной $S$ и основанием $PQ$ равнобедренный» и «В треугольнике $SPQ$ с вершиной $S$ и основанием $PQ$ $\angle P = \angle Q$» либо одновременно истинны, либо одновременно ложны.

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

Однако существуют операции, с помощью которых может быть выражена любая из пяти логических операций, которыми мы пользуемся. Такой операцией является, например, операция «Штрих Шеффера». Эта операция обозначается символом $X|Y$ и определяется следующей таблицей истинности:

$x$ $y$ $x|y$
1 1 0
1 0 1
0 1 1
0 0 1

Штрих Шеффера — функция, принимающая значение ложь, если $X$ – истинно и $Y$ – истинно. Очевидно, имеют место равносильности:

1) $\overline < X >\equiv X|X$

2) $X\wedge Y \equiv (X|Y)|(X|Y)$

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

Отметим, что $X|Y\equiv\overline < X\wedge Y >$.

Стрелка Пирса < функция Вебба >$X \downarrow Y$ – функция, принимающая значение истина, когда $X$ – ложно и $Y$ – ложно.

$x$ $y$ $x\downarrow y$
1 1 0
1 0 0
0 1 0
0 0 1

Отметим, что $X\downarrow Y = \overline < X >\wedge \overline < Y >= \overline < X \vee Y >$

Функция сложение по модулю 2 < функция разноименности, или сумма Жегалкина >$X\oplus Y$ — функция, принимающая значение истинно, когда $X$ и $Y$ принимают противоположные значения.

$x$ $y$ $x\oplus y$
1 1 0
1 0 1
0 1 1
0 0 0

Отметим, что $X\oplus Y = (\overline < X >\wedge Y)\vee (X\wedge\overline < Y >)$

Итак, в математической логике для записи сложных высказываний используются следующие логические операции над простыми высказываниями:

$\sim $, $\leftrightarrow $− эквивалентно;

$\oplus $− либо, либо.

Практика

С помощью логических операций над высказываниями из заданной совокупности высказываний можно строить различные сложные высказывания. При этом порядок выполнения операций указывается скобками. Например, из трех высказываний $X, Y, Z$ можно построить высказывания

$(X\wedge Y)\vee Z$ и $X\rightarrow (\overline < Y\vee (X\wedge Z) >)$

Первое из них есть дизъюнкция конъюнкции $X, Y$ и отрицания выказывания $Z$, а второе высказывание есть импликация, посылкой которой является высказывание $X$, а заключением — отрицание дизъюнкции высказывания $Y$ и конъюнкции высказываний $X, Z$.

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

Высказывания обозначаются большими буквами латинского алфавита $A, B, C, …$

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

  1. Для отрицания скобки опускаются;
  2. $\And $ имеет приоритет перед $\vee , \rightarrow, \equiv $;
  3. $\vee $ имеет приоритет перед $\rightarrow, \equiv $;

В связи с этим формулы

$(X\wedge Y)\vee Z$ и $X\rightarrow (\overline < Y\vee (X\wedge Z) >)$

могут быть записаны так:

$X\wedge Y\vee Z$ и $X\rightarrow \overline < Y\vee X\wedge Z >$

Логическое значение формулы алгебры логики полностью определяется логическими значениями входящих в нее элементарных высказываний. Например, логическим значением формулы $\overline < X\wedge Z >\vee \overline < Z >$ в случае, если $X = 1, Y = 1, Z=0$ будет истина, то есть $\overline < X\wedge Y >\vee \overline < Z >= 1$.

Все возможные логические значения формулы, в зависимости от значений входящих в нее элементарных высказываний, могут быть описаны полностью с помощью таблицы истинности. Эта таблица будет содержать $2^n$ строк, где $n$ – количество переменных.

Например, для формулы $\overline < X >\vee Y\rightarrow X\wedge \overline < Y >$ таблица истинности имеет вид:

$x$ $y$ $\bar < x >$ $\bar < y >$ $\bar < x >\vee y$ $x\wedge \bar < y >$ $\bar < x >\vee y \rightarrow x \wedge \bar < y >$
1 1 0 0 1 0 0
1 0 0 1 0 1 1
0 1 1 0 1 0 0
0 0 1 1 1 0 0

Легко видеть, что, если формула содержит $n$ элементарных высказываний, то она принимает $2^ < n >$ значений, состоящих из нулей и единиц, или, что тоже, таблица содержит $2^ < n >$ строк.

Далее:

Лемма о построении множества $[F]_{x1,x2}$

Формула Гаусса — Остроградского

Замена переменных в двойном интеграле. Двойной интеграл в полярных координатах

Критерий полноты . Лемма о нелинейной функции

Свойства криволинейного интеграла второго рода

Вычисление поверхностного интеграла первого рода

Условия независимости криволинейного интеграла от пути интегрирования

Механические приложения двойного интеграла

Инвариантное определение дивергенции

Класс $L$. Теорема о замкнyтости класса $L$

Соленоидальное векторное поле

Вычисление площадей плоских областей

Теорема о предполных классах

Полином Жегалкина. Теорема о представлении в виде полинома Жегалкина

Примеры применения цилиндрических и сферических координат

Огравление $\Rightarrow $

04 сентября 2016, 12:58 проектирование км, кмд, кж Алгебра логики [Г.И. Просветов, Е.А. Фоминых, Ф.Г. Кораблёв] 0 25385 0

  • Теорема об алгоритме распознавания полноты
  • Равносильные формулы алгебры высказываний

Определение булевой функции

Элементы булева множества [math]1[/math] и [math]0[/math] обычно интерпретируют как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определенного смысла. Элементы декартова произведения [math]B^n[/math] называют булевыми векторами. Множество всех булевых функций от любого числа переменных часто обозначается [math]P_2[/math] , а от n переменных — [math]P_2(n)[/math] . Булевы функции названы так по фамилии математика Джорджа Буля.

Основные сведения

Определение:
А́рность (англ. arity) функции — количество ее аргументов.

Каждая булева функция арности [math]n[/math] полностью определяется заданием своих значений на своей области определения, то есть на всех булевых векторах длины [math]n[/math] . Число таких векторов равно [math]2^n[/math] . Поскольку на каждом векторе булева функция может принимать значение либо [math]0[/math] , либо [math]1[/math] , то количество всех n-арных булевых функций равно [math]^n[/math] . То, что каждая булева функция задаётся конечным массивом данных, позволяет представлять их в виде таблиц. Такие таблицы носят название таблиц истинности и в общем случае имеют вид:

Таблица истинности
[math]x_1[/math] [math]x_2[/math] [math]\ldots[/math] [math]x_n[/math] [math]f(x_1,x_2,\ldots,x_n)[/math]
[math]0[/math] [math]0[/math] [math]\ldots[/math] [math]0[/math] [math]f(0,0,\ldots,0)[/math]
[math]1[/math] [math]0[/math] [math]\ldots[/math] [math]0[/math] [math]f(1,0,\ldots,0)[/math]
[math]0[/math] [math]1[/math] [math]\ldots[/math] [math]0[/math] [math]f(0,1,\ldots,0)[/math]
[math]1[/math] [math]1[/math] [math]\ldots[/math] [math]0[/math] [math]f(1,1,\ldots,0)[/math]
[math]\vdots[/math] [math]\vdots[/math] [math]\vdots[/math] [math]\vdots[/math] [math]\vdots[/math]
[math]0[/math] [math]1[/math] [math]\ldots[/math] [math]1[/math] [math]f(0,1,\ldots,1)[/math]
[math]1[/math] [math]1[/math] [math]\ldots[/math] [math]1[/math] [math]f(1,1,\ldots,1)[/math]

Практически все булевы функции малых арностей ( [math]0, 1, 2[/math] и [math]3[/math] ) сложились исторически и имеют конкретные имена. Если значение функции не зависит от одной из переменных (то есть строго говоря для любых двух булевых векторов, отличающихся лишь в значении этой переменной, значение функции на них совпадает), то эта переменная называется фиктивной (англ. dummy variable).

Нульарные функции

При [math]n = 0[/math] количество булевых функций равно [math]^0 = 2^1 = 2[/math] , первая из них тождественно равна [math]0[/math] , а вторая [math]1[/math] . Их называют булевыми константами — тождественный нуль и тождественная единица.

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

При [math]n = 1[/math] число булевых функций равно [math]^1 = 2^2 = 4[/math] .

Таблица значений булевых функций от одной переменной:

Функции от одной переменной
[math]0[/math] [math]x[/math] [math]\neg x[/math] [math]1[/math]
0 [math]0[/math] [math]0[/math] [math]1[/math] [math]1[/math]
1 [math]0[/math] [math]1[/math] [math]0[/math] [math]1[/math]
Сохраняет 0
Сохраняет 1
Самодвойственная
Монотонная
Линейная

Названия булевых функций от одной переменной:

Обозначение Название
[math]0[/math] тождественный ноль, тождественная ложь, тождественное «НЕТ»
[math]x[/math] тождественная функция, логическое «ДА», «YES»(англ.)
[math]\bar x,\ \neg x,\ x'[/math] отрицание, логическое «НЕТ», «НЕ», «НИ», «NOT»(англ.), «NO»(англ.)
[math]1[/math] тождественная единица, тождественная истина, тождественное «ДА», тавтология

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

При [math]n = 2[/math] число булевых функций равно [math]^2 = 2^4 = 16[/math] .

Таблица значений булевых функций от двух переменных:

Функции от двух переменных:
x y [math]0[/math] [math]x \land y[/math] [math]x \nrightarrow y[/math] [math]x[/math] [math]x \nleftarrow y[/math] [math]y[/math] [math]x \oplus y[/math] [math]x \lor y[/math] [math]x \downarrow y[/math] [math]x = y[/math] [math]\neg y[/math] [math]x \leftarrow y[/math] [math]\neg x[/math] [math]x \rightarrow y[/math] [math]x \triangledown y[/math] [math]1[/math]
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
Сохраняет 0
Сохраняет 1
Самодвойственная
Монотонная
Линейная

Названия булевых функций от двух переменных:

Обозначение Другие обозначения Название
[math]0[/math] тождественный ноль, тождественная ложь, тождественное «НЕТ»
[math]x \land y[/math] [math]x \cdot y,\ xy,\ x \And y,\ x\ AND\ y,\ AND(x, y),\ min(x, y), x [/math] И [math]y,[/math] И [math](x, y)[/math] 2И, конъюнкция
[math]x \nrightarrow y[/math] [math]x \gt y,\ \neg(x \rightarrow y),\ x\ GT\ y,\ GT(x,\ y)[/math] больше, инверсия прямой импликации
[math]x[/math] [math]YES1(x,y),[/math] ДА1 [math](x, y)[/math] первый операнд
[math]x \nleftarrow y[/math] [math]x \lt y,\ \neg(x \leftarrow y),\ x\ LT\ y,\ LT(x, y)[/math] меньше, инверсия обратной импликации
[math]y[/math] [math]YES2(x, y),[/math] ДА2 [math](x, y)[/math] второй операнд
[math]x \oplus y[/math] [math]x + _2 y,\ x \not = y,\ x \gt \lt y,\ x \lt \gt y,\ x\ XOR\ y,\ XOR(x,y)[/math] сложение по модулю 2, не равно, ксор, исключающее «или»
[math]x \lor y[/math] [math]x + y,\ x\ OR\ y,\ OR(x,y),\ max(x,y),[/math] [math]x [/math] ИЛИ [math]y,[/math] ИЛИ [math](x, y)[/math] 2ИЛИ, дизъюнкция
[math]x \downarrow y[/math] [math]x\ NOR\ y,\ NOR(x,y)[/math] [math]x [/math] ИЛИ-НЕ [math]y,[/math] ИЛИ-НЕ [math](x, y)[/math] НЕ-2ИЛИ, 2ИЛИ-НЕ, антидизъюнкция, функция Да́ггера, функция Ве́бба, стрелка Пи́рса
[math]x = y[/math] [math]x \equiv y, x EQV y, EQV(x,y), x \sim y, x \leftrightarrow y[/math] равенство, эквивалентность
[math]\neg y[/math] [math]NOT2(x, y),\ y’,\ \bar,[/math] НЕ2 [math](x, y)[/math] отрицание (негация, инверсия) второго операнда
[math]x \leftarrow y[/math] [math]x \geq y,\ x \subset y,\ x\ GE\ y,\ GE(x, y)[/math] больше или равно, обратная импликация (от второго аргумента к первому)
[math]\neg x[/math] [math]NOT1(x,y),\ x’,\ \bar,[/math] НЕ1 [math](x, y)[/math] отрицание (негация, инверсия) первого операнда
[math]x \rightarrow y[/math] [math]x \leq y,\ x \supset y,\ x\ LE\ y,\ LE(x,y)[/math] меньше или равно, прямая (материальная) импликация (от первого аргумента ко второму)
[math]x \triangledown y[/math] [math]x \mid y,\ x\ NAND\ y,\ NAND(x,y),[/math] [math]x [/math] И-НЕ [math]y,[/math] И-НЕ [math](x, y)[/math] НЕ-2И, 2И-НЕ, антиконъюнкция, Штрих Шеффера
[math]1[/math] тождественная единица, тождественная истина, тождественное «ДА», тавтология

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

При [math]n = 3[/math] число булевых функций равно [math]^3 = 2^8 = 256[/math] . Некоторые из них определены в следующей таблице:

Таблица истинности некоторых тернарных функций
[math]x[/math] [math]y[/math] [math]z[/math] [math]x \downarrow y \downarrow z[/math] [math]\neg (\geq 2(x,y,z))[/math] [math]x \not = y \not = z[/math] [math]x \mid y \mid z[/math] [math]min(x,y,z)[/math] [math]x=y=z[/math] [math]x \oplus y \oplus z[/math] [math]\geq 2(x,y,z)[/math] [math]f_1[/math] [math]f_2[/math] [math]max(x,y,z)[/math]
0 0 0 1 1 0 1 0 1 0 0 0 0 0
0 0 1 0 1 1 1 0 0 1 0 0 0 1
0 1 0 0 1 1 1 0 0 1 0 0 0 1
0 1 1 0 0 1 1 0 0 0 1 1 1 1
1 0 0 0 1 1 1 0 0 1 0 1 0 1
1 0 1 0 0 1 1 0 0 0 1 0 1 1
1 1 0 0 0 1 1 0 0 0 1 1 1 1
1 1 1 0 0 0 0 1 1 1 1 1 1 1

Названия булевых функций трех переменных:

Обозначения Другие обозначения Названия
[math]x \downarrow y \downarrow z[/math] [math]\downarrow (x,y,z) = Webb_2 (x,y,z)[/math] 3-ИЛИ-НЕ, функция Вебба, функция Даггера, стрелка Пирса
[math]\neg (\geq 2(x,y,z))[/math] Переключатель по большинству с инверсией, 3-ППБ-НЕ, мажоритарный клапан с инверсией
[math]x \not = y \not = z[/math] [math][\not =(x,y,z)] = NE(x,y,z)[/math] Неравенство
[math]x \mid y \mid z[/math] [math]\mid(x,y,z)[/math] 3-И-НЕ, штрих Шеффера
[math]x \land y \land z[/math] [math]\land (x,y,z) = (x\ AND\ y\ AND\ z) = AND(x,y,z) = min(x,y,z) = \lt br/\gt (x[/math] И [math] y[/math] И [math] z) = [/math] И [math](x,y,z)[/math] 3-И, минимум
[math]x=y=z[/math] [math][=(x,y,z)] = EQV(x,y,z)[/math] Равенство
[math]x \oplus y \oplus z[/math] [math]x +_2 y +_2 z = \oplus (x,y,z) = +_2 (x,y,z)[/math] Тернарное сложение по модулю 2
[math]\geq 2(x,y,z)[/math] [math](x [/math] И [math]y) [/math] ИЛИ [math](y[/math] И [math] z)[/math] ИЛИ [math](z [/math] И [math] x)[/math] переключатель по большинству, 3-ППБ, мажоритарный клапан
[math]f_1[/math] Разряд займа при тернарном вычитании
[math]f_2[/math] Разряд переноса при тернарном сложении
[math]x+y+z[/math] [math]+(x,y,z) = max(x,y,z) = (x\ OR\ y\ OR\ z) = OR(x,y,z) = (x [/math] ИЛИ [math] y [/math] ИЛИ [math] z) = [/math] ИЛИ [math](x,y,z)[/math] 3-ИЛИ, максимум

Представление функции формулой

Определение:
Если выбрать некоторый набор булевых функций [math]A[/math] , то с использованием выбранных функций можно записать некоторые другие булевы функции. Такая запись булевой функции называется формулой (англ. formula).

Например, если [math]A = \left\<\land,\neg\right\>[/math] , то функция [math]a \lor b[/math] представляется в виде [math]\neg(\neg a \land \neg b)[/math]

Тождественность и двойственность

Определение:
Две булевы функции тождественны (англ. identical) друг другу, если на любых одинаковых наборах аргументов они принимают равные значения.

Тождественность функций f и g можно записать, например, так:
[math]f(x_1, x_2, \dots, x_n)=g(x_1, x_2, \dots, x_n)[/math]

Просмотрев таблицы истинности булевых функций, легко получить такие тождества:

[math]\overline=1[/math] [math]\overline=0[/math] [math]\overline<\overline>=x[/math] [math]x \land y=y \land x\![/math] [math]x\lor y=y \lor x[/math]
[math]0 \land x=0\![/math] [math]1 \land x=x\![/math] [math]0 \lor x=x[/math] [math]1\lor x=1[/math] [math]x \land x=x \lor x=x[/math]

А проверка таблиц, построенных для некоторых суперпозиций, даст следующие результаты:

[math]x \land \overline=0[/math] [math]x \lor \overline=1[/math]
[math]\overline=\overline\lor\overline[/math] [math]\overline\land\overline=\overline[/math] (законы де Моргана)

[math]x \land (y\lor z)=(x \land y)\lor (x \land z)[/math]
[math]x \lor (y \land z)=(x\lor y) \land (x\lor z)[/math] (дистрибутивность конъюнкции и дизъюнкции)

Определение:
Функция [math]g(x_1,x_2,\dots,x_n)[/math] называется двойственной (англ. duality) функции [math]f(x_1,x_2,\dots,x_n)[/math] , если [math]f(\overline,\overline,\dots,\overline)=\overline[/math] .

Легко показать, что в этом равенстве [math]f[/math] и [math]g[/math] можно поменять местами, то есть функции [math]f[/math] и [math]g[/math] двойственны друг другу. Из простейших функций двойственны друг другу константы [math]0[/math] и [math]1[/math] , а из законов де Моргана следует двойственность конъюнкции и дизъюнкции. Тождественная функция, как и функция отрицания, двойственна сама себе.

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

Суперпозиции

Основная статья: Суперпозиции

Определение:
Суперпозиция функций, композиция функций (англ. function composition) — функция, полученная из некоторого множества функций путем подстановки одной функции в другую или отождествления переменных.

Множество всех возможных не эквивалентных друг другу суперпозиций данного множества функций образует замыкание данного множества функций.

Пусть нам дан некоторый набор булевых функций [math]K[/math] . Получить новую функцию, являющеюся композицией функций из [math]K[/math] , мы можем следующими способами:

  • Подстановкой одной функции в качестве некоторого аргумента для другой;
  • Отождествлением аргументов функций.

Полнота системы, критерий Поста

Основная статья: Теорема Поста о полной системе функций

Определение:
Замыкание множества функций (англ. сlosure) — подмножество всех булевых функций, что любую из этих функций можно выразить через функции исходного множества.
Определение:
Множество булевых функций называется полной системой (англ. complete set), если замыкание этого множества совпадает с множеством всех функций.

Американский математик Эмиль Пост [1] сформулировал необходимое и достаточное условие полноты системы булевых функций. Для этого он ввел в рассмотрение следующие замкнутые классы булевых функций:

  • функции, сохраняющие константу [math]T_0[/math] и [math]T_1[/math] ,
  • самодвойственныые функции [math]S[/math] ,
  • монотонные функции [math]M[/math] ,
  • линейные функции [math]L[/math] .

Набор булевых функций [math]K[/math] является полным тогда и только тогда, когда он не содержится полностью ни в одном из классов [math] S,M,L,T_0,T_1 [/math] , иными словами, когда в нем имеется хотя бы одна функция, не сохраняющая ноль, хотя бы одна функция, не сохраняющая один, хотя бы одна несамодвойственная функция, хотя бы одна немонотонная функция и хотя бы одна нелинейная функция.

Представление булевых функций

Теорема Поста открывает путь к представлению булевых функций синтаксическим способом, который в ряде случаев оказывается намного удобнее чем таблицы истинности. Отправной точкой здесь служит нахождение некоторой полной системы функций [math]\Sigma = \[/math] . Тогда каждая булева функция сможет быть представлена некоторым термом в сигнатуре [math]\Sigma[/math] , который в данном случае называют также формулой. Относительно выбраной системы функций полезно знать ответы на следующие вопросы:

  • Как построить по данной функции представляющую её формулу?
  • Как проверить, что две разные формулы эквивалентны, то есть задают одну и ту же функцию?
    • В частности: существует ли способ приведения произвольной формулы к эквивалентной её канонической форме, такой что, две формулы эквивалентны тогда и только тогда, когда их канонические формы совпадают?

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

    Дизъюнктивная нормальная форма (ДНФ)

    Основная статья: ДНФ

    Определение:
    Дизъюнктивная нормальная форма (ДНФ) (англ. disjunctive normal form, DNF) — нормальная форма, в которой булева функция задана как дизъюнкция некоторого числа простых конъюнктов.

    Любая булева формула благодаря использованию закона двойного отрицания, закона де Моргана и закона дистрибутивности может быть записана в ДНФ.

    Примеры ДНФ:

    [math]f(x,y,z) = (x \land y) \lor (y \land \neg )[/math] .

    [math]f(x,y,z,t,m) = (x \land z) \lor (y \land x \land \neg) \lor (x \land \neg ) [/math] .

    Конъюнктивная нормальная форма (КНФ)

    Основная статья: КНФ

    Определение:
    Конъюнктивная нормальная форма, КНФ (англ. conjunctive normal form, CNF) — нормальная форма, в которой булева функция имеет вид конъюнкции нескольких простых дизъюнктов.

    Любая булева формула с помощью использования закона двойного отрицания, закона де Моргана и закона дистрибутивности может быть записана в КНФ.

    [math]f(x,y,z) = (x \lor y) \land (y \lor \neg)[/math]

    [math]f(x,y,z,t) = (x \lor t) \land (y \lor \neg) \land (\neg \lor \neg) \land (\neg \lor \neg \lor z)[/math]

    [math]f(x,y,z,t,m) = (x \lor m \lor \neg) \land (y \lor \neg) \land (y \lor t \lor \neg)[/math]

    Полином Жегалкина

    Основная статья: Полином Жегалкина

    Определение:
    Полином Жегалкина (англ. Zhegalkin polynomial) — полином с коэффициентами вида [math]0[/math] и [math]1[/math] , где в качестве произведения берётся конъюнкция, а в качестве сложения исключающее или.

    Полином Жегалкина имеет следующий вид:

    [math]P = a_ <000\ldots000>\oplus a_ <100\ldots0>x_1 \oplus a_ <010\ldots0>x_2 \oplus \ldots \oplus a_ <00\ldots01>x_n \oplus a_ <110\ldots0>x_1 x_2 \oplus \ldots \oplus a_ <00\ldots011>x_ x_n \oplus \ldots \oplus a_ <11\ldots1>x_1 x_2 \ldots x_n [/math]

    С помощью полинома Жегалкина можно выразить любую булеву функцию, так как он строится из следующего набора функций: [math]\bigl\langle \wedge, \oplus, 1 \bigr\rangle[/math] , который, в свою очередь, по теореме Поста является полным.

    [math]f(x_1,x_2) = 1 \oplus x_1 \oplus x_1 x_2 [/math]

    [math]f(x_1,x_2,x_3) = x_1 \oplus x_1 x_2 \oplus x_2 x_3 [/math]

    [math]f(x_1,x_2,x_3,x_4) = 1 \oplus x_1 \oplus x_4 \oplus x_1 x_2 \oplus x_1 x_4 \oplus x_2 x_4 \oplus x_1 x_2 x_4 [/math]

    Тождественные функции. Выражение функций друг через друга

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

    Приведение тождественной функции есть выражение булевой функции через другие.

    Запись булевой функции в ДНФ, КНФ, а также выражение с помощью полинома Жегалкина — способы выражения одних булевых функций через другие.

    Пример:
    Выразим следующие функции через систему функций [math]\ <\land, \lor, \lnot \>[/math] .

    [math] x \oplus y = \left ( x \land \lnot y \right ) \lor \left ( \lnot x \land y \right ) = \left ( x \lor \lnot y \right ) \land \left ( \lnot x \lor y \right )[/math]

    [math] x \downarrow y = \lnot \left ( x \lor y \right) = \lnot x \land \lnot y[/math]

    Подстановка одной функции в другую

    Определение:
    Подстановкой (англ. substitution) функции [math]g[/math] в функцию [math]f[/math] называется замена [math]i[/math] -того аргумента функции [math]f[/math] значением функции [math]g[/math] : [math]h(x_, \ldots, x_) = f(x_, \ldots, x_, g(x_, \ldots, x_), x_, \ldots, x_)[/math]

    Допускается также не только подстановка одной функции в другую, но и подстановка функции в саму себя.

    При подстановке функции [math]g[/math] вместо [math]i[/math] -того аргумента функции [math]f[/math] , результирующая функция [math]h[/math] будет принимать аргументы, которые можно разделить на следующие блоки:

    1. [math] x_, \ldots, x_[/math] — аргументы функции [math]f[/math] до подставленного значения функции [math]g[/math]
    2. [math] x_, \ldots, x_ [/math] — используются как аргументы для вычисления значения функции [math]g(y_, \ldots, y_)[/math]
    3. [math] x_, \ldots, x_ [/math] — аргументы функции [math]f[/math] после подставленного значения функции [math]g[/math]
    1. [math] f(a,b) = a \vee b [/math]
    2. [math] g(a) = \neg a [/math]

    Отождествление переменных

    Определение:
    Отождествлением переменных (англ. identification of variables) называется подстановка [math]i[/math] -того аргумента функции [math]f[/math] вместо [math]j[/math] -того аргумента: [math]h(x_, \ldots, x_, x_, \ldots, x_) = f(x_, \ldots, x_, \ldots, x_, x_, x_, \ldots, x_)[/math]

    Таким образом, при отождествлении [math]c[/math] переменных мы получаем функцию [math]h[/math] с количеством аргументов [math]n-c+1[/math] .

    Пример:
    [math] f(a,b) = a \vee b [/math] — исходная функция

    [math] h(a) = a \vee a [/math] — функция с отождествленными первым и вторым аргументами

    Схемы из функциональных элементов

    Основная статья: Реализация булевой функции схемой из функциональных элементов

    Определение:
    Схема из функциональных элементов, логическая схема (англ. logic diagram) — размеченный ориентированный граф без циклов, в некотором базисе [math]B[/math] , в котором:

    1. вершины, в которые не входят ребра, называются входами схемы, и каждая из них помечена некоторой переменной (разным вершинам соответствуют разные переменные);

    Отождествление переменных осуществляется при помощи ветвления проводников.

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

    Некоторые логические элементы:

    И ИЛИ НЕ Штрих Шеффера Стрелка Пирса

    Стандартный базис

    Определение:
    Стандартный базис — система булевых функций: [math]\ <\land, \lor, \lnot \>[/math]

    Если рассматривать множество бинарных булевых функций [math]P_2(2)[/math] , то для выражения любой булевой функции данного множества (кроме стрелки Пирса и штриха Шеффера) через стандартный базис достаточно выразить тождественные функции для эквиваленции, импликации и константы [math] 0 [/math] с использованием функций, принадлежащих стандартному базису, т. к. все остальные операции можно выразить через данные 3 функции с помощью отрицания:

    [math] x \leftrightarrow y = \left ( x \rightarrow y \right ) \land \left ( y \rightarrow x \right ) [/math]

    [math] x \rightarrow y = \lnot x \lor y [/math]

    [math] 0 = x \land \lnot x [/math]

    Функции [math] \mid \ и \downarrow[/math] являются отрицаниями функций [math] \land \ и \ \lor[/math] соответственно.

    [math] x \mid y = \lnot \left ( x \land y \right )[/math]

    [math] x \downarrow y = \lnot \left ( x \lor y \right )[/math]

    Тождественность функций можно доказать с помощью таблицы истинности.

    Выразим через стандартный базис обратную импликацию [math] \left (x \leftarrow y \right ) [/math] .

    [math]x \leftarrow y = \lnot x \rightarrow \lnot y = x \lor \lnot y [/math]

    Полнота стандартного базиса

    Стандартный базис является полной системой булевых функций

    [math] x \land y = \lnot \left (\lnot x \lor \lnot y \right ) [/math]

    [math] x \lor y = \lnot \left (\lnot x \land \lnot y \right ) [/math]

    Следовательно, стандартный базис является избыточным, в то время как безызбыточными являются подмножества системы:

    [math] \ < \land , \lnot \>[/math] (конъюнктивный базис Буля)

    [math] \ < \lor , \lnot \>[/math] (дизъюнктивный базис Буля)

    Теоремы о числе функций в базисе

    Максимально возможное число булевых функций в безызбыточном базисе — четыре.

    Рассмотрим произвольный безызбыточный базис [math] X[/math] . Тогда по теореме Поста [math]X[/math] содержит следующие функции (не обязательно различные):

    [math]f_0 \notin T_0, f_1 \notin T_1, f_s \notin S, f_m \notin M, f_l \notin L[/math] , где [math] T_0, T_1, S, M, L[/math] — классы Поста.

    Значит, так как [math]X[/math] — безызбыточный базис, а система [math]\[/math] — полная, то [math]\left | X \right | \le 5[/math]

    Рассмотрим [math]f_0[/math] . Возможны два случая:

    1. [math] f_0(1, 1, \ldots, 1) = 0 [/math] , тогда [math]f_0[/math] также не сохраняет единицу и немонотонная, т.е.

    [math] f_0 = f_1 = f_m [/math] . Значит, [math]\left | X \right | \le 3[/math] .

    2. [math] f_0(1, 1, \ldots, 1) = 1 [/math] , тогда [math]f_0[/math] несамодвойственная, т.е.

    Для любого числа [math]k, 1 \le k \le 4 [/math] найдётся базис [math] X[/math] , что [math]\left | X \right | = k[/math] .

    Приведём примеры базисов для каждого [math]k[/math] :

    [math]k = 1 \Rightarrow X = \< \downarrow \>[/math] ;

    [math]k = 2 \Rightarrow X = \< \lnot, \land \>[/math] ;

    Докажем, что последняя система является базисом:

    [math] 0 \notin T_1[/math] ;

    [math] 1 \notin T_0[/math] ;

    [math] x\land y \notin L\ и\ S[/math] ;

    [math] x\oplus y\oplus z \notin M[/math]

    См. также

    • Специальные формы КНФ
    • Сокращенная и минимальная ДНФ
    • Пороговая функция
    • Cумматор
    • Полные системы функций. Теорема Поста о полной системе функций

    Примечания

    Источники информации

    • Гаврилов Г. П., Сапоженко А. А. Сборник задач по дискретной математике. — М.: Наука, 1969.
    • Кузнецов О. П., Адельсон-Вельский Г. М. Дискретная математика для инженера. — М.: «Энергия», 1980. — 344 с.
    • Марченков С. С. Замкнутые классы булевых функций. — М.: Физматлит, 2000.
    • Яблонский С. В. Введение в дискретную математику. — М.: Наука, 1986.
    • Алексеев В. Б. Дискретная математика (курс лекций, II семестр). Сост. А. Д. Поспелов
    • Быкова С. В., Буркатовская Ю. Б., Булевы функции, учебно-методический комплекс, Томск, 2006
    • Учебные пособия кафедры математической кибернетики ВМиК МГУ
    • Булева функция — Википедия
    • http://psi-logic.narod.ru/bool/bool.htm
    • Дискретная математика и алгоритмы
    • Булевы функции

    Решение 15 задания ЕГЭ по информатике про основные законы Алгебры Логики

    15-е задание: «Основные законы алгебры логики»
    Уровень сложности — повышенный,
    Требуется использование специализированного программного обеспечения — нет,
    Максимальный балл — 1,
    Примерное время выполнения — 5 минут.

    Проверяемые элементы содержания: Знание основных понятий и законов математической логики

    До ЕГЭ 2021 года — это было задание № 18 ЕГЭ
    Типичные ошибки и рекомендации по их предотвращению:

    «Важно понимать, что выражение должно быть тождественно истинно, т.е. истинно при любых допустимых значениях переменных x и у, а не только при некоторых наборах значений»

    ФГБНУ «Федеральный институт педагогических измерений»

    Элементы математической логики

      Для решения 15 задания, потребуется знание таблиц истинности.

    Для выполнения задания рекомендуется повторить следующие темы:

    Преобразование логических операций:
    A → B = ¬ A ∨ B
    или
    A → B = A + B
    A ↔ B = A ⊕ B = A ∧ B ∨ A ∧ B
    или
    A ↔ B = A ⊕ B = A · B + A · B
    A ⊕ B = (¬A ∧ B) ∨ (A ∧ ¬B)
    или
    A ⊕ B = ( A · B) + (A · B )
    Законы алгебры логики:
    A ∧ ¬ A = 0 или A · A = 0
    A ∨ ¬ A = 1 или A + A = 1
    A ∧ A = A или A · A = A
    A ∨ A = A или A + A = A
    A ∧ 0 = 0
    A ∧ 1 = A
    A ∨ 0 = A
    A ∨ 1 = 1
    A ∧ B = B ∧ A
    A ∨ B = B ∨ A
    (A ∧ B) ∧ C = A ∧ (B ∧ C)
    (A ∨ B) ∨ С = A ∨ (B ∨ С)

    (A ∧ B) ∨ C = (A ∨ C) ∧ (B ∨ C)
    (A ∨ B) ∧ С = (A ∧ С) ∨ (B ∧ С)
    и наоборот:
    (A ∨ B) ∧ (A ∨ C) = A ∨ (B ∧ C)
    (A ∧ B) ∨ (A ∧ C) = A ∧ (B ∨ C)

    ¬ (A ∧ B) = ¬ A ∨ ¬ B
    ¬ (A ∨ B) = ¬ A ∧ ¬ B
    (A ∧ B) ∨(¬A ∧ B) = B
    (A ∨ B) ∧(¬A ∨ B) = B

    A ∨ A ∧ B = A
    A ∧ (A ∨ B) = A
    A ∨ ¬A ∧ B = A ∨ B
    ¬A ∨ A ∧ B = ¬A ∨ B
    A ∧ (¬A ∨ B) = A ∧ B
    ¬A ∧ (A ∨ B) = ¬A ∧ B

    1. выражения в скобках,
    2. операции «НЕ»,
    3. операции «И»,
    4. операции «ИЛИ»,
    5. операции «импликация»
    6. операции «эквиваленция»

    A → B → C → D = ((A → B) → C) → D

    Математическая логика и теория множеств

    • пересечение множеств соответствует логическому умножению, а объединение – логическому сложению;
    • пересечением двух множеств называется новое множество, состоящее из элементов, принадлежащих одновременно обеим множествам:

    пересечение множеств
    Пример:
    пример пересечения множеств

    пример объединения множеств

    Пример:

    универсальное множество

    X ∨ U = U и X ∧ U = X

    разность двух множеств
    Пример разности множеств:
    пример разности множеств

    дополнение множества

    Для большей определенности стоит рассмотреть тему круги Эйлера

    Задания с отрезками и ДЕЛ

    Для решения заданий необходимо знать рассмотренную тему о множествах.

    Для упрощения решений можно пользоваться следующими законами.

    1. Если в задании формула тождественно истинна (равна 1), и
    2. после упрощения A без отрицания
    то используется закон:

    где B — известная часть выражения.

    1. Если в задании формула тождественно истинна (равна 1), и
    2. после упрощения A с отрицанием
    то используется закон:

    где B — известная часть выражения.

    1. Если в задании формула тождественно ложна (равна 0), и
    2. после упрощения A без отрицания
    то используется закон:

    где B — известная часть выражения.

    1. Если в задании формула тождественно ложна (равна 0), и
    2. после упрощения A с отрицанием
    то используется закон:

    Задания с поразрядной конъюнкцией

    В задании 15 ЕГЭ встречаются задачи, связанные с поразрядной конъюнкцией.
    Например:

    5 & 26

    означает поразрядную конъюнкцию (логическое «И») между двоичными значениями двух чисел — 5 и 26. Выполняется так:

    5 = 1012 26 = 110102 0 = 000002 

    Задания, связанные с поразрядной конъюнкцией, решаются несколькими способами. Рассмотрим один из них.

    (x & K = 0) как Zk 

    свойство 1:
    Zk * Zm = Zk or m

    (X & 5 = 0)  (X & 26 = 0)
    Z5 ∧ Z26 
    Z5 ∧ Z26 = Z26 or 5 помним, что дизъюнкция - это операция логическое "ИЛИ" (сложение) 5 = 1012 26 = 110102 31 = 111112 
    Z5 ∧ Z26 = Z31 

    свойство 2:
    Zk + Zm = Zk and m

    (X & 28 = 0)  (X & 22 = 0)
    Z28 ∨ Z22 
    Z28 ∨ Z22 = Z28 and 22 помним, что конъюнкция - это операция логическое "И" (умножение) 28 = 111002 22 = 101102 101002 = 2010 
    Z28 ∨ Z22 = Z20 

    свойство 3:

    Условие Zk → Zm истинно для любых натуральных значений x тогда и только тогда, когда все единичные биты двоичной записи числа M входят во множество единичных битов двоичной записи числа K.

    • На деле, это означает, что если имеем:
    X & 29 = 0  X & 5 = 0 Истинно или Ложно? 
    Z29 → Z5 
    Z29 → Z5 = 1 (истине), тогда, когда: 29 = 111012 5 = 1012 единичные биты двоичного числа 5 входят в единичные биты двоичного числа 29 (совпадают с ними)
    Z29 → Z5 = 1 (истинно)

    свойство 4:
    (x & 125 = 5) то же самое, что и
    Z120 * ¬Z4 * ¬Z1 = 1 (истине)

    • Так, например, если в задании имеем:
    X & 130 = 3
    X & 130 = 3 то же самое, что и Z127 * ¬Z2 * ¬Z1 т.е. 3 = 2 + 1 : 2 = 10 1 = 01 3 = 11

    Решение заданий 15 ЕГЭ по информатике

    Плейлист видеоразборов задания на YouTube:

    Задания с множествами

    15_16:

    № 95
    Элементами множества А являются натуральные числа. Известно, что выражение

    ((x ∈ ) → ¬(x ∈ )) ∨ (x ∈ A)

    истинно (т. е. принимает значение 1) при любом значении переменной х .

    Определите наименьшее возможное значение суммы элементов множества A .

      ✎ Решение аналитическое:
    P ≡ (x ∈ ) ; Q ≡ (x ∈ ) ; A ≡ (x ∈ A).
    (P → ¬Q) ∨ A = 1 Избавимся от импликации: ¬P ∨ ¬Q ∨ A = 1
    ¬P ∨ ¬QА = 1 0 1 
    ¬P ∨ ¬Q = 0, или ¬P = 0 отсюда P = 1 ¬Q = 0 отсюда Q = 1
    3 + 9 = 12

    ✎ Решение программированием:
    PascalAbc.net:

    begin var s1 := hset(1, 3, 5, 7, 9, 11); var s2 := hset(3, 6, 9, 12); var a:=new List; for var x := 1 to 100 do begin if (x in s1 
    

    Ответ: 12

    �� Видеорешение на RuTube здесь

    15_17:

    Элементами множества А являются натуральные числа. Известно, что выражение

    (x ∈ ) → (((x ∈ ) ∧ ¬(x ∈ A)) → → ¬(x ∈ ))

    истинно (т. е. принимает значение 1) при любом значении переменной х .

    Определите наименьшее возможное значение суммы элементов множества A .

      ✎ Теоретическое решение:
    P≡(x ∈ ) ; Q ≡ (x ∈ ) ; A ≡ (x ∈ A).
    P → ((Q ∧ ¬A)  ¬P) = P  (¬(Q ∧ ¬А)  ¬P) = ¬P  (¬(Q ∧ ¬А) ∨ ¬P) = ¬P  ¬Q ∨ А.
    ¬P ∨ ¬QА = 1 0 1 
    ¬P ∨ ¬Q = 0, или ¬P = 0 отсюда P = 1 ¬Q = 0 отсюда Q = 1
    6 + 12 = 18

    Ответ: 18

    15_18: Закон распределения

    Элементами множеств А , P , Q являются натуральные числа, причём P = , Q = . Известно, что выражение

    ( (x ∈ A) → (x ∈ P) ) ∧ ( (x ∈ Q) → ¬(x ∈ A) )

    истинно (т. е. принимает значение 1) при любом значении переменной х .

    Определите наибольшее возможное количество элементов в множестве A .

      ✎ Теоретическое решение:
    P ≡ (x ∈ P); Q ≡ (x ∈ Q); A ≡ (x ∈ A).
    Избавимся от импликации: (¬A ∨ P) ∧ (¬Q ∨ ¬A) = 1 Применим распределительный закон (но можно вывести самостоятельно): ¬A ∨ (P ∧ ¬Q) = 1
    ¬A(P ∧ ¬Q) = 1 0 1 
    P ∧ ¬Q = 1, или P = 1 и ¬Q = 1 отсюда Q = 0

    Ответ: 7

    15_20: Закон поглощения

    № 100
    Элементами множества А являются натуральные числа. Известно, что выражение

    ¬(x ∈ A) →¬(x ∈ ) ∨ (¬(x ∈ ) ∧ (x ∈ ))

    истинно (т. е. принимает значение 1) при любом значении переменной х .

    Определите наименьшее возможное количество элементов множества A.

      ✎ Теоретическое решение:
    P ≡ (x ∈ ); Q ≡ (x ∈ ); A ≡ (x ∈ A).
    Избавимся от импликации: A ∨ ¬P ∨ (¬Q ∧ P) = 1 Применим закон поглощения (но можно вывести самостоятельно): A ∨ ¬P ∨ ¬Q = 1
    A¬P ∨ ¬Q = 1 1 0 
    ¬P ∨ ¬Q = 0, или P = 1 и Q = 1

    Ответ: 1

    Задания с отрезками на числовой прямой

    Отрезки на числовой прямой:

    15_3:

    На числовой прямой даны два отрезка: P=[44,48] и Q=[23,35].

    Укажите наибольшую возможную длину отрезка А, для которого формула

    ((x ϵ P) → (x ϵ Q)) ∧ (x ϵ A)

    тождественно ложна, то есть принимает значение 0 при любом значении переменной x.

    ✍ Решение:

    ✎ Теоретическое решение (логическое):

      Упростим формулу, избавившись от 'x ϵ':

    (P → Q) ∧ A

    правило импликации: a → b = ¬a ∨ b

    (¬P ∨ Q) ∧ A

    решение 15 задания егэ по информатике

    (¬P ∨ Q) ∧ A = 0
    (¬P ∨ Q) ∧ A 0  0 = 0 0  1 = 0 1  0 = 0 1  1 = 1 
    1. (¬P ∨ Q) = 1 ∨ 0 = 1 - на данном отрезке А должно равняться 0 2. (¬P ∨ Q) = 1 ∨ 1 = 1 - на данном отрезке А должно равняться 0 3. (¬P ∨ Q) = 1 ∨ 0 = 1 - на данном отрезке А должно равняться 0 4. (¬P ∨ Q) = 0 ∨ 0 = 0 - на данном отрезке А может! равняться 1 5. (¬P ∨ Q) = 1 ∨ 0 = 1 - на данном отрезке А должно равняться 0 
    48 - 44 = 4

    Результат: 4
    ✎ Решение программированием

    Важно: Этот способ подходит НЕ для всех заданий с отрезками!

    def f(a1,a2,x): return((44<=x<=48)<=(23<=x<=35))and(a1<=x<=a2) maxim = 0 for a1 in range (1,200): for a2 in range (a1+1,200): if all(f(a1,a2,x)==0 for x in range (1,200)):# если все ложны if a2-a1>maxim: maxim=a2-a1 print(a1,a2, a2-a1) # сами точки отрезка и длина
    44 45 1 44 46 2 44 47 3 44 48 4 

    PascalABC.net (классическое решение):

    begin var s1:=44..48; var s2:=23..35; var a:=new List; for var x:=1 to 1000 do begin var p:=x in s1; var q:=x in s2; if not (p<=q) = true then a.Add(x); end; a.count.print end.

    С подробным аналитическим решением задания 15 ЕГЭ по информатике можно ознакомиться по видео:

    �� YouTube здесь
    �� Видеорешение на RuTube здесь

    Отрезки на числовой прямой:

    15_9:

    На числовой прямой даны два отрезка: P = [10,20] и Q = [30,40].

    Укажите наибольшую возможную длину отрезка A, для которого формула

    ((x ∈ P) → (x ∈ Q)) → ¬(x ∈ A)

    тождественно истинна, то есть принимает значение 1 при любом значении переменной x.

    ✍ Решение:

    ✎ Теоретическое решение (логическое):

      Упростим выражение, введя обозначения:

    A: x ∈ A P: x ∈ P Q: x ∈ Q
    (P → Q) → ¬A = 1
    (P → Q) → ¬A = 1 => ¬(P → Q) ∨ ¬A = 1 => ¬(¬P ∨ Q) ∨ ¬A = 1
    ¬(¬P ∨ Q) ∨ ¬A = 1 => P ∧ ¬Q ∨ ¬A = 1
    А = 1 P = 1 ¬Q = 1 или Q = 0 

    решение 15 задания ЕГЭ с числовой приямой

    Результат: 10

    ✎ Решение программированием

    Важно: Этот способ подходит НЕ для всех заданий с отрезками!

    PascalABC.net (классическое решение):

    ## var s1:=10..20; var s2:=30..40; var a:=new List; for var x:=1 to 1000 do begin var p:=x in s1; var q:=x in s2; if not(p<=q) = true then a.Add(x); end; a.Println; print(a.Count-1) // так как требуется длина отрезка
    10 11 12 13 14 15 16 17 18 19 20 10

    Результат: 10

    Отрезки на числовой прямой:

    15_10:

    На числовой прямой даны два отрезка: P = [3, 20] и Q = [6, 12].

    Укажите наибольшую возможную длину отрезка A, для которого формула

    ((x ∈ P) ~ (x ∈ Q)) → ¬(x ∈ A)

    тождественно истинна, то есть принимает значение 1 при любом значении переменной x.

    ✍ Решение:

    ✎ Теоретическое решение (логическое):

      Упростим выражение, введя обозначения:

    A: x ∈ A P: x ∈ P Q: x ∈ Q
    (P ~ Q) → ¬A = 1
    (P ~ Q) → ¬A = 1 => ¬(P ~ Q) ∨ ¬A = 1

    Далее возможно 2 способа решения.

    (a ~ b) = a * b + ¬a * ¬b

    ¬(P ~ Q) = ¬((P ∧ Q) ∨ (¬P ∧ ¬Q)) = = ¬(P ∧ Q) ∧ ¬(¬P ∧ ¬Q)
    ¬(P ∧ Q) ∧ ¬(¬P ∧ ¬Q) = = ¬(P ∧ Q) ∧ (P ∨ Q)
    ¬(P ∧ Q) ∧ (P ∨ Q) ∨ ¬A = 1
    ¬(P ∧ Q) ∧ (P ∨ Q) = 1 А = 1

    15 задание ЕГЭ отрезки

    ✎ 2 способ:
    После того, как мы избавились от импликации, имеем:

    ¬(P ~ Q) ∨ ¬A = 1

    Результат: 8

    С решением задания 15 вы также можете ознакомиться, посмотрев видео (аналитическое решение):

    �� YouTube здесь
    �� Видеорешение на RuTube здесь

    Отрезки на числовой прямой:

    15_11:

    На числовой прямой даны два отрезка: P = [11, 21] и Q = [15, 40].

    Укажите наибольшую возможную длину отрезка A, для которого формула

    (x ∈ A) → ¬((x ∈ P) ~ (x ∈ Q))

    тождественно истинна, то есть принимает значение 1 при любом значении переменной x.

    ✍ Решение:

    ✎ Теоретическое решение (логическое):

      Упростим выражение, введя обозначения:

    A: x ∈ A P: x ∈ P Q: x ∈ Q
    A → ¬(P ~ Q) = 1
    A → ¬(P ~ Q) = 1 => ¬A ∨ ¬(P ~ Q) = 1

    15 задание отрезки на числовой прямой

    Результат: 19

    Задания с ДЕЛ

    Поиск наибольшего А, известная часть Дел ∨ Дел = 1

    15_7:

    Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».

    Для какого наибольшего натурального числа А формула

     (ДЕЛ(x, 40) ∨ ДЕЛ(x, 64)) → ДЕЛ(x, A) 

    тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?

    ✍ Решение:

    ✎ Теоретическое решение (логическое):
    ✎ Способ 1:

    A = ДЕЛ(x,A); D40 = ДЕЛ(x, 40); D64 = ДЕЛ(x, 64)
    (D40 ∨ D64) → A = 1
    ¬(D40 ∨ D64) ∨ A = 1 или (¬D40 ∧ ¬D64) ∨ A = 1
    (¬D40 ∧ ¬D64) ∨ A = 1 1 2 
    ¬D40 ∧ ¬D64 = 0 или ¬(¬D40 ∧ ¬D64) = 1 Преобразуем по закону Де Моргана и получим: D40 ∨ D64 = 1

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

    x/A : x/40 ∨ x/64
    x = 40, 64, 80, 120, 128, 160, 192, 200, .
    А = 1, 2, 4, 8
    НОД (40,64) = 8 40,64 (64 - 40 = 24) 40,24 (40 - 24 = 16) 24,16 (24 - 16 = 8) 16,8 (16 - 8 = 8) 8,8

    ✎ Теоретическое решение с помощью кругов Эйлера:

    64 / 40 = 1 (24 остаток) 40 / 24 = 1 (16 остаток) 24 / 16 = 1 (8 остаток) 16 / 8 = 2 (0 остаток) - НОД = 8 +++ 40 / 8 = 5 64 / 8 = 8

    2

    Результат: 8

    ✎ Решение программированием:
    Python:

    for A in range(1,500): OK = 1 for x in range(1,1000): OK *= ((x % 40 == 0) or (x % 64 == 0))<=(x % A== 0) if OK: print( A )
    1 2 4 8 
    ## function f(a,x:integer):= (x.Divs(40) or (x.Divs(64)) (1..1000).All(x->f(a,x))).print;
    1 2 4 8 

    PascalABC.net (классическое решение):

    begin for var A := 1 to 500 do begin var ok := 1; for var x := 1 to 1000 do begin if (((x mod 40 = 0) or (x mod 64 = 0)) 
    
    1 2 4 8 

    Результат: 8

    Поиск наименьшего А, известная часть Дел ∧ ¬Дел = 1

    15_5:

    Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».

    Для какого наименьшего натурального числа А формула

    ДЕЛ(x, A) → (¬ДЕЛ(x, 28) ∨ ДЕЛ(x, 42))

    тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?

    ✍ Решение:

    ✎ Теоретическое решение (логическое):

    ДЕЛ(x, A) → (¬ДЕЛ(x, 28) ∨ ДЕЛ(x, 42)) = 1
    A = ДЕЛ(x,A); D28 = ДЕЛ(x, 28); D42 = ДЕЛ(x, 42)
    A → (¬D28 ∨ D42) = 1

    Избавимся от импликации:

    ¬A ∨ (¬D28 ∨ D42) = 1
    ¬A ∨ (¬D28 ∨ D42) = 1 1 2 
    (¬D28 ∨ D42) = 0 один случай: когда ¬D28 = 0 и D42 = 0
    x/¬A : x/28 ∧ x/¬42
    x = 28, 56, 84, 112, 140, 168, 196, 224, .
    А = 1, 2, 3

    ✎ Решение программированием. Язык Python, Pascal:

      Из общего выражения:

    ДЕЛ(x, A) → (¬ДЕЛ(x, 28) ∨ ДЕЛ(x, 42)) = 1
    for A in range(1,50): OK = 1 for x in range(1,1000): OK *= (x % A == 0) 
    
    ## function f(a,x:integer):= x.Divs(a) (1..1000).All(x->f(a,x))).take(1).print;

    PascalABC.net (классическое решение):

    begin for var A := 1 to 50 do begin var ok := 1; for var x := 1 to 1000 do begin if (x mod A = 0) 0)or (x mod 42 = 0)) = false then begin ok := 0; break; end; end; if (ok = 1) then begin print(A); break; end end; end.

    OK - переменная-индикатор: если находится такое А при котором, диапазон всех значений x , подставленных в выражение, возвращает истинное значение выражения, то ОК остается равным 1, т.к. используется операция умножения (до цикла ОК необходимо присвоить единице).
    Следует иметь в виду, что в программировании вместо операции импликация ( -> ) можно использовать нестрогое неравенство: . Т.к. таблица истинности для операции импликация соответствует операции

    a b F(a<=b) 0 0 1 0 1 1 1 0 0 1 1 1

    Результат: 3

    15_6:

    Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».

    Для какого наименьшего натурального числа А формула

     (¬ДЕЛ(x, 19) ∨ ¬ДЕЛ(x, 15)) → ¬ДЕЛ(x, A) 

    тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?

    ✍ Решение:

    ✎ Теоретическое решение (логическое):

    A = ДЕЛ(x,A); D19 = ДЕЛ(x, 19); D15 = ДЕЛ(x, 15)
    (¬D19 ∨ ¬D15) → ¬A = 1
    D19 ∧ D15 ∨ ¬A = 1
    ¬A ∨ D19 ∧ D15 = 1 1 2 
    ¬A ∨ D19 ∧ D15 = 1 0  1 = 1 
    ¬A = 0 при D19 ∧ D15 = 1 или A = 1 при D19 = 1 и D15 = 1 
    A = 1 D19 = 1 D15 = 1
    19 * 2 = 38 (38 не делится на 15) 19 * 3 = 57 (57 не делится на 15) 19 * 4 = 76 (76 не делится на 15) 19 * 5 = 95 (95 не делится на 15) . 19 * 10 = 190 (190 не делится на 15) 19 * 15 = 285 (285 делится на 15)
    x = 1, 2, 3. 15, 16, 17, 18, 19, 20, 21, 22, 23, . 30, .
    А = 1, 2, 3, . 285

    ✎ Решение программированием:

      Из общего выражения:

     (¬ДЕЛ(x, 19) ∨ ¬ДЕЛ(x, 15)) → ¬ДЕЛ(x, A) = 1
    for A in range(1,500): OK = 1 for x in range(1,1000): OK *= ((x % 19 != 0) or (x % 15 != 0))
    

    OK - переменная-индикатор: если находится такое А при котором, диапазон всех значений x , подставленных в выражение, возвращает истинное значение выражения, то ОК остается равным 1, т.к. используется операция умножения (до цикла ОК необходимо присвоить единице).
    Следует иметь в виду, что в программировании вместо операции импликация ( -> ) можно использовать нестрогое неравенство: . Т.к. таблица истинности для операции импликация соответствует операции

    a b F(a<=b) 0 0 1 0 1 1 1 0 0 1 1 1
    ## function f(a,x:integer):= x.Divs(a) (1..1000).All(x->f(a,x))).take(1).print;

    Результат: 285

    Задания с поразрядной конъюнкцией

    15_1:

    Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 12&6 = 11002&01102 = 01002 = 4

    Для какого наименьшего неотрицательного целого числа A формула

    (X & A = 0) ∧ ¬(X & 35 ≠ 0 → X & 52 ≠ 0)

    тождественно ложна (то есть принимает значение 0 при любом неотрицательном значении переменной X)?

    ✍ Решение:

    Стоит заметить, что для такого типа задач, нет универсального единственного решения. Поэтому на видео, расположенном ниже, представлено два варианта решения.
    ✎ Способ 1 (теоретическое решение):
    Рассмотрим один из вариантов решения:

      Удалим из формулы X&, чтобы сократить ее запись:

    (A = 0) ∧ ¬(35 ≠ 0 → 52 ≠ 0)
    (A = 0)  ¬(35 ≠ 0 → 52 ≠ 0)
    (A = 0) ∧ ¬(35 ≠ 0 → 52 ≠ 0) 1 2 

    правило импликации: a → b = ¬a ∨ b

    (A = 0) ∧ ¬(35 = 0 ∨ 52 ≠ 0) т.к. в результате получается отрицание того, что 35 ≠ 0, то убираем знак "не равно": было 35 ≠ 0, стало 35 = 0 

    закон де Моргана: ¬ (A ∨ B) = ¬ A ∧ ¬ B

    A = 0 ∧ 35 ≠ 0 ∧ 52 = 0 = 0
    0 ∧ 0 = 0 0 ∧ 1 = 0 1 ∧ 0 = 0 1 ∧ 1 = 1
    (A = 0) ∧ 35 ≠ 0 ∧ 52 = 0 = 0 0  1 = 0 
    35 ≠ 0 ∧ 52 = 0 = истинно (=1) если: 35 ≠ 0 = истинно (=1) и 52 = 0 = истинно (=1) так как стоит логическое умножение  - смотрим выше таблицу истинности для конъюнкции
    35 ≠ 0 = 1 (истина) и 52 = 0 = 1 (истина) и A = 0 = 0 (ложь)
    35: 100011 (≠ 0) 52: 110100 (= 0)
    52 1 1 0 1 0 0
    X 0 0 ? 0 ? ?
    35 1 0 0 0 1 1
    X 1 ? ? ? 1 1
    0 0 ? 0 ? ? & 1 ? ? ? 1 1 0 0 ? 0 1 1 
    X 0 0 ? 0 1 1
    A 0 0 0 0 1 1
    0000112 = 310

    Ответ: 3

    ✎ Способ 2* (теоретическое решение):

      Используем метод А.В. Здвижковой.

    1. Произвести замену (x & K = 0) на Zk
    2. Выполнить преобразования по свойству импликации и закону Де Моргана.
    3. Стремиться прийти к выражению с конъюнкциями без отрицаний типа: Zk * Zm .
    4. Все выражения типа Zk * Zm преобразовать по свойству
      Zk * Zm = Zk or m .
    5. Путем преобразований прийти к импликации: Zk → Zm .
    A ∧ ¬(¬Z35 → ¬Z52) = 0
    ¬(A ∧ ¬(¬Z35 → ¬Z52)) = 1
    ¬A ∨ (¬Z35 → ¬Z52) = 1
    ¬A ∨ (Z35 ∨ ¬Z52) = 1
    ¬A ∨ ¬Z52 ∨ Z35 = 1
    ¬(A ∧ Z52) ∨ Z35 = 1
    (A ∧ Z52) → Z35 = 1
    ZA ∨ 52 → Z35 = 1

    Условие Zk → Zm истинно для любых натуральных значений x тогда и только тогда, когда все единичные биты двоичной записи числа M входят во множество единичных битов двоичной записи числа K.

    A = ??0?11 52 = 110100 A or 52 = 110111 35 = 100011 
    Аmin = 112 = 310

    ✎ Решение программированием
    PascalAbc.net (LINQ):

    ## function f(a,x:integer):= ((x and A)=0) and not(not(x and 35=0) (1..2000).All(x->f(a,x)=false)).print;

    PascalAbc.net (классическое решение):

    begin for var a:=1 to 1000 do begin var ok:=1; for var x:=1 to 1000 do begin var f1:=(x and a)=0; var f2:=(x and 35)=0; var f3:=(x and 52)=0; if f1 and not (not f2
    

    Результат: 3

    Детальный разбор данного задания 15 ЕГЭ по информатике предлагаем посмотреть на видео:

    Вариант решения №1 (универсальный, теоретический):
    �� YouTube здесь
    �� Видеорешение на RuTube здесь

    Вариант решения №2 (не универсальный, но простой):
    �� YouTube здесь

    15_2:

    Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 12&6 = 11002&01102 = 01002 = 4


    Для какого наибольшего неотрицательного целого числа A формула

    X & A ≠ 0 → (X & 36 = 0 → X & 6 ≠ 0)

    тождественно истинна (то есть принимает значение 1 при любом неотрицательном значении переменной X)?

    ✍ Решение:

      ✎ Способ 1 (теоретическое решение):
    z36 = (x&36 = 0), z6 = (x&6 = 0), A = (x&A = 0)
    ¬A → (z36 → ¬ z6)
    ¬A → (z36 → ¬ z6) = A + ¬z36 + ¬z6
    A + ¬z36 + ¬z6 = A + ¬(z36 * z6)
    A + ¬(z36 * z6) = ¬(z36 * z6) + A = (z36 * z6) → A
    z36 * z6 = z36 or 6
    1001002 -> 36 1102 -> 6 100100 110 1001102 -> 36 or 6 = 3810 
    z38 → A
    A = 1001102 = 3810

    ✎ Способ 2 (теоретическое решение):

    x&A ≠ 0 → (x&36 = 0 → x&6 ≠ 0) = 1
    A = (x&A = 0); P = (x&36 = 0); Q = (x&6 = 0);
    ¬A → (P → ¬Q) = 1
    A ∨ (¬P ∨ ¬Q) = 1
    A ∨ (¬P ∨ ¬Q) = 1; или 1 ∨ (0) = 1 
    ¬P ∨ ¬Q = 0 Отсюда имеем: ¬P = 0 и ¬Q = 0 (дизъюнкция равна 0 в единственном случае, когда все операнды равны 0)
    Q = 1 и P = 1
    100100 : 36 000110 : 6 0**0** : маска P (x&36 = 0) ***00* : маска Q (x&6 = 0)
    0**0** : маска P (x&36 = 0) ***00* : маска Q (x&6 = 0) 0**00* : общая маска x *00**0 : маска для A (x&A = 0) т.е. в тех битах А, где может получиться единица (звездочки в обеих масках), 
    мы поставили нули.
    100110 = 3810 

    ✎ Решение программированием
    PascalAbc.net (LINQ):

    ## function f(a,x:integer):= not(x and A=0) <=((x and 36=0) <= not(x and 6=0))?true:false; (1..2000).Where(a->(1..2000).All(x->f(a,x))).print;

    PascalAbc.net (классическое решение):

    begin for var a:=1 to 1000 do begin var ok:=1; for var x:=1 to 1000 do begin var f1:=(x and a)<>0; var f2:=(x and 36)=0; var f3:=(x and 6)<>0; if f1 
    

    Результат: 38

    Подробное решение данного задания 15 ЕГЭ по информатике предлагаем посмотреть в видео уроке:
    Способ 1:
    �� YouTube здесь
    �� Видеорешение на RuTube здесь
    Способ 2:
    �� YouTube здесь
    �� Видеорешение на RuTube здесь

    Поразрядная конъюнкция:

    15_8:

    № 209
    Определите наименьшее натуральное число А из интервала [43, 55], такое, что выражение

    ((x & 17 ≠ 0) → ((x & A ≠ 0) → (x & 58 ≠ 0))) → → ((x & 8 = 0) ∧ (x & A ≠ 0) ∧ (x & 58 = 0))

    тождественно ложно (то есть принимает значение 0 при любом натуральном значении переменной х)?

    ✍ Решение:

    ✎ Решение теоретическим способом:

      Кратко изложенное решение *:

    (¬Z17 → (¬A → ¬Z58)) → (z8 ∧ ¬A ∧ Z58) = 0
    ¬(((¬Z17 → (¬A → ¬Z58)) → (z8 ∧ ¬A ∧ Z58)) = 1
    Z8 ∧ Z58 = Z8 or 58 : 8 = 1000 or 58 = 111010 111010 = 58
    Z8 ∧ Z58 = Z58
    ¬(¬(Z17 ∨ A ∨ ¬Z58) ∨ (¬A ∧ Z58)) = 1
    (Z17 ∨ A ∨ ¬Z58) ∧ ¬(¬A ∧ Z58)) = 1
    (Z17 ∨ A ∨ ¬Z58) ∧ (A ∨ ¬Z58) = 1
    A ∨ ¬Z58 = 1
    ¬Z58 ∨ A => Z58 → A = 1
    43 = 101011 - не подходит! 58 = 111010 44 = 101100 - не подходит! 58 = 111010 45 = 101101 - не подходит! 58 = 111010 46 = 101110 - не подходит! 58 = 111010 47 = 101111 - не подходит! 58 = 111010 48 = 110000 - подходит! 58 = 111010

    Результат: 48
    ✎ Решение программированием:
    PascalAbc.net (LINQ):

    ## function f(a,x:integer):= (not(x and 17=0) <=(not(x and a=0) <= not(x and 58=0))) <= ((x and 8 = 0) and (not(x and a = 0)) and (x and 58=0))?true:false; (43..55).Where(a->(1..2000).All(x->f(a,x)=false)).print;

    PascalAbc.net (классическое решение):

    begin for var a:=43 to 55 do begin var ok:=1; for var x:=1 to 1000 do begin var f1:=x and 17<>0; var f2:=x and a<>0; var f3:=x and 58<>0; var f4:=x and 8 = 0; var f5:=x and a<>0; var f6:=x and 58=0; if f1 
    

    Результат: 48

    15_15:

    № 173
    Определите набольшее натуральное число A, такое что выражение

    ((x & 26 = 0) ∨ (x & 13 = 0)) → ((x & 78 ≠ 0) → (x & A = 0))

    тождественно истинно (то есть принимает значение 1 при любом натуральном значении переменной х)?

    ✍ Решение:

    ✎ Решение теоретическим способом:

      Для упрощения восприятия введем обозначения:

    z26 = (x & 26 = 0) z13 = (x & 13 = 0) z78 = (x & 78 = 0) A = (x & A = 0)
    (z26 ∨ z13) → (¬z78 → A) = 1
    (z26 ∨ z13) → (z78 ∨ A) = 1
    26 : 11010 единичные биты: 4, 3, 1 13 : 1101 единичные биты: 3, 2, 0 ∧ =------------------------ 01000 = 810 
    z8 → (z78 ∨ A) z78: не влияет на решение, так как операция дизъюнкция истинна тогда, когда хотя бы один операнд истинен z8 → A : . 
    Наибольшее А = 1000 = 810 

    Результат: 8
    ✎ Решение программированием:
    PascalAbc.net (LINQ):

    ## function f(a,x:integer):= ((x and 26=0) or (x and 13=0)) (1..2000).All(x->f(a,x))).print;

    PascalAbc.net (классическое решение):

    begin for var a:=1 to 1000 do begin var ok:=1; for var x:=1 to 1000 do begin var f1:=x and 26=0; var f2:=x and 13=0; var f3:=x and 78<>0; var f4:=x and a=0; if (f1 or f2) 
    

    Результат: 8

    Задания на поиск наибольшего или наименьшего числа А


    Поиск наибольшего или наименьшего числа А:

    15_4: 15 задание. Демоверсия ЕГЭ 2018 информатика:

    демоверсия егэ 2018 решение 15 (18) задания

    Для какого наибольшего целого числа А формула

    тождественно истинна, то есть принимает значение 1 при любых целых неотрицательных x и y?

    ✎ Способ 1 (программный):
    Pascalabc.net (LINQ - решение запросом):
    ## function f(a,x,y:integer):= ((x<=9)<=(x*x<=a)) and ((y*y<=a) <= (y <=9))?true:false; (-1000..1000).Where(a->(0..1000).All(x->(0..1000).All(y->f(a,x,y)))).print;

    Pascalabc.net (классическое решение методом перебора):

    Важно: Поскольку используется метод полного перебора, то возможна ситуация, когда транслятор будет работать слишком медленно. Но работоспособность представленного алгоритма проверена на онлайн компиляторах.

    begin for var A := 200 downto -100 do begin var OK := 1; for var x := 0 to 100 do for var y := 0 to 100 do if ((x 
    
    for A in range(200,-100,-1): OK = 1 for x in range(0,100): for y in range(0,100): OK *= ((x<=9) <= (x*x<=A)) and((y*y<=A) <= (y<=9)) if OK: print(A) break

    ✎ Способ 2 (теоретическое решение):

      Условно разделим исходное выражение на части:

    решение 15 (18) задания демоверсии егэ информатика

    (импликация 0 → 0 = 1)

    y > 9 y2 > A при любых y 
    возьмем наименьшее возможное по условию натуральное: y = 10, тогда A < 100

    Результат: 99

    Подробное решение 15 задания демоверсии ЕГЭ 2018 года смотрите на видео (аналитическое решение):

    �� YouTube здесь
    �� Видеорешение на RuTube здесь

    Поиск наибольшего или наименьшего числа А:

    15_12: Досрочный егэ по информатике 2018, вариант 1:

    Укажите наименьшее значение А, при котором выражение

    (y + 3x < A) ∨ (x >20) ∨ (y > 40)

    истинно для любых целых положительных значений x и y.

    ✍ Решение:

    ✎ Способ 1 (программный):
    Pascalabc.net (LINQ - решение запросом):

    ## function f(a,x,y:integer):= (y+3*x20) or (y >40)?true:false; (-1000..1000).Where(a->(1..1000).All(x->(1..1000).All(y->f(a,x,y)))).Take(1).print;

    Pascalabc.net (классическое решение методом перебора):

    Важно: Поскольку используется метод полного перебора, то возможна ситуация, когда транслятор будет работать слишком медленно. Но работоспособность представленного алгоритма проверена на онлайн компиляторах.

    begin for var A := -100 to 200 do begin var OK := 1; for var x := 1 to 100 do for var y := 1 to 100 do if ((y+3*x20)or(y>40)) = false then begin OK := 0; break; end; if OK = 1 then begin print(A); break end; end; end.
    for A in range(-100,200): OK = 1 for x in range(1,100): for y in range(1,100): OK *= (y+3*x 20) or (y > 40) if OK: print(A) break

    ✎ Способ 2 (теоретическое решение):

      Определим основные части выражения, выделив отдельно неизвестную часть - с А, и, так сказать, известную часть, то есть остальную.

    1 2 (y+3x < A)∨ (x > 20) ∨ (y > 40)
    (y+3x < A)∨ (x > 20) ∨ (y > 40) 1 или 0? 1 = 1 Не подходит!
    1. (y+3x < A) = 1 2. (x >20) ∨ (y > 40) = 0
    А > 3x + y A > 3*20 + 40 A > 100

    ✎ Данное задание также можно решить графическим способом
    Выбрав произвольное значение A и представив А > 3x + y как прямую на плоскости.
    Результат: 101

    Подробное решение досрочного ЕГЭ 2018 года смотрите на видео (аналитическое решение):

    �� YouTube здесь
    �� Видеорешение на RuTube здесь

    Поиск наибольшего или наименьшего числа А:

    15_0: Разбор 15 задания. Демоверсия егэ по информатике 2019:

    Для какого наибольшего целого неотрицательного числа А выражение

    (48 ≠ y + 2x) ∨ (A ✎ Решение 1 (программный способ):
    Pascalabc.net (LINQ - решение запросом):

    ## function f(a,x,y:integer):= (48 <> y+2*x) or (a(0..1000).All(x->(0..1000).All(y->f(a,x,y)))).print;

    Python (классическое решение методом перебора):

    for A in range(200,0,-1): OK = 1 for x in range(0,100): for y in range(0,100): OK *= (48!=y+2*x) or(A
    

    ✎ Решение 2 (графический способ):

      Разделим общее выражение на две части. Выделим неизвестную часть красным:

    (48 ≠ y + 2x) ∨ (A < x) ∨ (A < y)
    (48 ≠ y + 2x) ∨ (A < x) ∨ (A < y)= 1 0 1 
    y + 2x = 48 : при x = 0, y = 48 при y = 0, 2x = 48 => x = 24

    решение 15 (18) задания демоверсии егэ 2019

    Результат: 15

    Видео решения 15 задания демоверсии ЕГЭ 2019 (аналитическое решение):
    �� YouTube здесь
    �� Видеорешение на RuTube здесь

    Поиск наибольшего или наименьшего числа А:

    15_19:

    Для какого наименьшего целого числа А формула

    (y + 5x 4) ∨ (y ✎ Способ 1 (программный):
    Python:

    for A in range(-100,100): OK = 1 for x in range(0,100): for y in range(0,100): OK *= (y+5*x<=34)<=((y-x >4)or(y<=A)) if OK: print( A ) break

    Pascalabc.net (LINQ - решение запросом):

    ## function f(a,x,y:integer):= (y+5*x<=34) <=((y-x>4) or (y<=a))?true:false; (0..1000).Where(a->(0..1000).All(x->(0..1000).All(y->f(a,x,y)))).take(1).print;

    Pascalabc.net (классическое решение методом перебора):

    begin for var A := -100 to 100 do begin var OK := true; for var x := 0 to 100 do begin for var y := 0 to 100 do begin OK := (y + 5 * x 4) or (y 
    

    Результат: 9

    ✎ Способ 2 (теоретическое решение):

    ¬(y + 5x 4) ∨ (y 
    
    ¬(y + 5x 4)(y = 1 1 часть 2 часть 
    ¬(y + 5x 4)(y = 1 1 часть = 0 2 часть = 1 
    y + 5x > 34 = 0, значит: 1. y + 5x y - x > 4 = 0, значит: 2. y - x 
    y A >= y 

    решение

    34 - 5x = 4 + x 30 = 6x x = 5 Найдем y: y = 4 + 5 = 9
    y = 9: A >= 9 => наименьшее A = 9 

    Результат: 9

    Поиск наибольшего или наименьшего числа А:

    15_13:

    № 296
    Укажите наименьшее целое значение А при котором выражение

    (2y + 5x 100) ∨ (3x – 2y > 70)

    истинно для любых целых положительных значений x и y.

    ✍ Решение:

      ✎ Способ 1 (программный):
      Python (классическое решение методом перебора):

    for A in range(-200,200): OK = 1 for x in range(1,100): for y in range(1,100): OK *= (2*y + 5*x < A) or (2*x + 4*y >100) or (3*x - 2*y > 70) if OK: print( A ) break

    Pascalabc.net (LINQ - решение запросом):

    ## function f(a,x,y:integer):= (2*y+5*x100) or (3*x-2*y>70)?true:false; (-1000..1000).Where(a->(1..1000).All(x->(1..1000).All(y->f(a,x,y)))).take(1).print;

    PascalABC.NET (классическое решение методом перебора):

    begin for var A := -200 to 200 do begin var OK := true; for var x := 1 to 100 do begin for var y := 1 to 100 do begin OK := (2*y + 5*x < A) or (2*x + 4*y >100) or (3*x - 2*y > 70); if OK = false then break; end; if OK = false then break; end; if OK then begin print(A); break; end; end; end.

    ✎ Способ 2 (графический): представлен в видеоразборе ниже.
    Результат: 171

    Видео разбора задания смотрите на видео (аналитическое решение):

    �� YouTube здесь
    �� Видеорешение на RuTube здесь

    Поиск наибольшего или наименьшего числа А:

    15_14:

    № 303
    Укажите наибольшее целое значение А при котором выражение

    (3y – x > A) ∨ (2x + 3y ✎ Способ 1 (графическое решение):

    (3y – x > A)(2x + 3y < 30) ∨ (2y – x < –31)= 1
    (1) (2x + 3y) >= 30, y >= (30 - 2x) / 3 x = (30 - 3y) /2
    (2) (2y – x >=–31) y >= (x - 31) / 2 x = 2y + 31
    (1) x | y 0 | 10 15| 0
    (2) x | y 0 | -15 ( целые) 30|0

    если y = 1, то x = 2*1 + 31 = 33

    ✎ Способ 2 (программный):
    Pascalabc.net (LINQ - решение запросом):

    ## function f(a,x,y:integer):= (3*y-x>a) or (2*x+3*y<30) or (2*y-x<-31)?true:false; (-100..1000).Where(a->(1..1000).All(x->(1..1000).All(y->f(a,x,y)))).print;

    Python (классическое решение методом перебора):

    for A in range(200,-200,-1): OK = 1 for x in range(1,100): for y in range(1,100): OK *= (3*y-x>A) or (2*x+3*y<30) or (2*y-x<-31) if OK: print(A) break

    Результат: -31

    Смотрите решение подобного задания:

    �� YouTube здесь
    �� Видеорешение на RuTube здесь

    15_21:

    Известно, что для некоторого отрезка А формула

    ((x ∈ A) → (x2 2 
    

    тождественно истинна (то есть принимает значение 1 при всех вещественных значениях переменной x).
    Какую наибольшую длину может иметь отрезок A?

      ✎ Способ 1 (теоретическое решение):
    ((x ∈ A) → (x2((x2 = 1
    1) ((x ∈ A) → (x2 2 
    
    1) ((x ∉ A) ∨ (x2 2 > 16) ∨ (x ∈ A)) = 1
    1) ((x ∉ A)(x2 = 1 true false 
    1) x ∉ A, для x2 > 100 => x > 10, x < -10 =>x ∈ [-∞ ; -10), (10; ∞] То есть найден диапазон, в котором нет A.
    2) ((x2 > 16)(x ∈ A)) = 1 false true 
    (x ∈ A), для x2 x = -4 => x ∈ [-4;4]
    10+10 = 20

    Ответ: 20

    Смешанные выражения

    15_22:

    Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».
    Для какого наименьшего натурального числа А формула

    (ДЕЛ(x, 250) → ¬ ДЕЛ(x, 10)) ∨ (3x + 2A ≥ 1000)

    тождественно истинна, то есть принимает значение 1 при любом значении переменной х?

      ✎ Способ 1 (программный):
      Pascalabc.net (LINQ - решение запросом):
    ## function f(a,x:integer):= (x.divs(250) =1000)?true:false; (-1000..1000).Where(a->(1..1000).All(x->f(a,x))).Take(1).print;

    Ответ: 125

    * В некоторых задачах использован метод, предложенный А.В. Здвижковой

    17 комментариев для “Решение 15 задания ЕГЭ по информатике про основные законы Алгебры Логики”

    Спасибо. Все понятно!
    Почему в первой задаче длина отрезка 4,если в отрезок входят: 44,45,46,47,48. Т.е. пять цифр.

    я думал, что я один такой умный. Замечание правильное. Ответ = 5 .
    Потому что в задании сказано промежуток, а не отрезок. Крылов с Чуркиной тоже ошиблись ��
    Промежуток (математика)
    Промежуток, или более точно, промежуток числовой прямой — множество вещественных чисел, обладающее тем свойством, что вместе с любыми двумя числами содержит любое, лежащее между ними.
    В задаче имеется в виду конечно же промежуток не вещественных, а целых чисел.

    Спасибо) значит, исправим само задание: вместо «промежуток» укажем «отрезок»
    18_10 видео не соответствует задаче.
    26 в 10-ой =11010 в 2-ой
    А в целом большое спасибо!
    Спасибо:) исправлено

    Последняя задача (18_14.) не соответствует задаче в прикреплённом видеоролике, но ответ указан от задания в видео. Можно узнать правильный ответ?

    Там написано, что в видео объясняется подобное задание

    Простите, я не понимаю…
    В примере 130&x=3.
    130=10000010.
    Побитовая конъюнкция с каким числом даст 3.
    10000010 & xxxxxxxx =00000011
    Поразрядная конъюнкция с последним 0 всегда даст 0, то есть такого числа не существует.
    Или я чего-то не понимаю.

    каждый бит одного числа умножить на соответствующий ему бит другого числа — это поразрядная конъюнкция

    Добрый день!
    Разбираю теорию, исследую первое свойство поразрядной конъюкции. В нем Z(k) * Z(n) = Z(k or n), и здесь необходимо применять поразрядую дизъюнкцию. Обнаружила ошибку: 26 и 5 дадут 31, но в разобранном примере ответ равен 29. А все дело в том, что неверно представлено число 26 в 2 СС. Оно равно не 11000, а 11010.
    Прошу исправить ошибку, иначе школьники совсем запутаются!
    Спасибо)

    Спасибо большое! исправлено)

    Здравствуйте, В связи со свойством 4 у вас пара ошибок:
    1) У вас написано, что свойство верно для выражения x & 125 = 5, а применяете вы его к выражению X & 130 = 3, для которого неизвестно ещё ничего о его верности.
    2) В первом же шаге, у вас «замена» X & 130 = 3 на Z_130 = 3, но проведя обратную замену по определению над свойством 1, получим 3 = Z_130 = ( x & 130 = 1) — тождественно ложное утверждение в множестве натуральных чисел, т.к. 1 не равно 3 в множестве целых. И вообще, всем было бы проще и понятнее, если бы вы по-разному обозначали операции в булевой алгебре множеств (\cap, \cup), в кольце целых чисел (+, \times) и логические операции (логическое «или», логическое «и»). Вообще круто было бы ещё и нейтральные элементы обозначать по-разному, хотя бы для булевой алгебры множеств и всего остального.

    Спасибо большое! постараемся всё учесть)

    Все права защищены. Использование любых материалов сайта возможно только с разрешения правообладателя.
    По вопросам размещения рекламы на сайте - обращайтесь: mayersvetlana @ yandex.ru

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *