Разбор 2 задания егэ по информатике

Связь с естественным языком

Часто указывают на сходство между конъюнкцией и союзом «и» в естественном языке. Составное утверждение «A и B» считается истинным, когда истинны оба утверждения A и B, в противном случае составное утверждение ложно. Это в точности соответствует определению конъюнкции в булевой алгебре, если «истину» обозначать как 1{\displaystyle 1}, а «ложь» как {\displaystyle 0}. При этом часто делают стандартную оговорку о неоднозначности естественного языка. Например, в зависимости от контекста союз «и» может нести дополнительный оттенок «и тогда», «и поэтому», «и потом». Отличие логики естественного языка от математической остроумно выразил американский математик Стивен Клини, заметив, что в естественном языке «Мэри вышла замуж и родила ребенка» — не то же самое, что «Мэри родила ребенка и вышла замуж».

Программирование

В компьютерных языках используется два основных варианта конъюнкции: логическое «И» и побитовое (поразрядное) «И». Например, в языках C/C++ логическое «И» обозначается символом «&&», а побитовое — символом «&». В терминологии, используемой в C#, операцию «&» принято называть логическим «И», а операцию «&&» — условным «И», поскольку значения операндов являются условиями для продолжения вычисления. В языках Pascal/Delphi оба вида конъюнкции обозначаются с использованием ключевого слова «and», а результат действия определяется типом операндов. Если операнды имеют логический тип (например, Boolean) — выполняется логическая операция, если целочисленный (например, Byte) — поразрядная.

Логическое «И» применяется в операторах условного перехода или в аналогичных случаях, когда требуется получение результата false{\displaystyle false} или true{\displaystyle true}. Например:

if (a & b & c) 
{
    /* какие-то действия */
};

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

a = false; b = true; c = true;
if (a && b && c) 
{
    /* какие-то действия */ 
};

Проверка истинности выражения в данном случае остановится после проверки переменной a, так как дальнейшее сравнение не имеет смысла.

Результат будет равен true{\displaystyle true}, если оба операнда равны true{\displaystyle true} (для числовых типов не равны {\displaystyle 0}). В любом другом случае результат будет равен false{\displaystyle false}.

При этом применяется стандартное соглашение: если значение левого операнда равно false{\displaystyle false}, то значение правого операнда не вычисляется (вместо b{\displaystyle b} может стоять сложная формула). Такое соглашение ускоряет исполнение программы и служит полезным приёмом в некоторых случаях. Компилятор Delphi поддерживает специальную директиву, включающую

{$B-}

или выключающую

{$B+}

подобное поведение. Например, если левый операнд проверяет возможность вычисления правого операнда:

if (a !=  && b  a > 3) 
{
    /* какие-то действия */
};

В этом примере, благодаря проверке в левом операнде, в правом операнде никогда не произойдёт деления на ноль.

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

Примечания

1. ↑ , с. 264—266, 534—536.
2. , с. 67.
3. Стяжкин Н. И.  Формирование математической логики. — М.: Наука, 1967. — 508 с. — С. 321, 348, 352, 368.
4. , с. 30.
5. Пратт Т.  Языки программирования: разработка и реализация. — М.: Мир, 1979. — 574 с. — С. 352, 439.
6. Грогоно П.  Программирование на языке Паскаль. — М.: Мир, 1982. — 384 с. — С. 51.
7. Вегнер П.  Программирование на языке Ада. — М.: Мир, 1983. — 240 с. — С. 68.
8. Эллис М., Строуструп Б.  Справочное руководство по языку программирования C++ с комментариями. — М.: Мир, 1992. — 445 с. — ISBN 5-03-002868-4. — С. 65, 86—87.
9. Яблонский С. В.  Введение в дискретную математику. — М.: Наука, 1979. — 272 с. — С. 9—10, 37.
10. Рвачёв В. Л.  Теория R-функций и некоторые её приложения. — Киев: Наукова думка, 1982. — 552 с. — С. 38, 66.
11. ↑ Словарь по кибернетике. 2-е изд / Под ред. В. С. Михалевича. — Киев: Украинская советская энциклопедия, 1989. — 751 с. — ISBN 5-88500-008-5.

Примеры СДНФ для некоторых функций

Стрелка Пирса: $x \downarrow y = (\neg { x } \land \neg { y } )$

Исключающее или: $x \oplus y \oplus z = (\overline { x } \land \overline { y } \land z) \lor (\overline { x } \land y \land \overline { z } ) \lor (x \land \overline { y } \land \overline { z } ) \lor (x \land y \land z)$

Совершенной дизъюнктивной нормальной формой формулы $A(x_1,x_2,…,x_n)$ называется ДНФ, обладающая следующими свойствами:

а } в ней нет одинаковых дизъюнктивных элементов;

б } ни одна элементарная конъюнкция не содержит двух одинаковых высказываний;

в } ни какая элементарная конъюнкция не содержит высказывание вместе с ее отрицанием;

г } в каждой элементарной конъюнкции содержится либо $X_i$, либо $\overline { X } _i$, где $i = 1, n$.

Условие а } – г } являются необходимыми и достаточными для того, чтобы ДНФ стала СДНФ. В свою очередь эти условия дают возможность составить алгоритм получения СДНФ из ДНФ:

1) если какая-нибудь элементарная конъюнкция не содержит высказывание $X_i$, то заменим выражением $B\wedge (X_i\vee \overline { X } _i) \equiv (B\wedge X_i)\vee (B\wedge \overline { X } _i)$;

2) если в полученном выражении окажутся одинаковые элементарные конъюнкции, то лишние опускаются;

3) если в некоторых элементарных конъюнкциях окажутся одинаковые высказывания, то лишние опускаются;

4) удаляем элементарные конъюнкции, в которых содержатся высказывания вместе с их отрицанием.

Если все элементарные конъюнкции окажутся таковыми, т.е. вся формула будет ложной, то она не будет иметь СДНФ.

Если все элементарные конъюнкции окажутся таковыми, т.е. вся формула будет ложной, то она не будет иметь СДНФ.

Формула называется дизъюнктивной нормальной формой { ДНФ } , если она является дизъюнкцией неповторяющихся элементарных конъюнкций. ДНФ записываются в виде: $A_1\vee A_2\vee …\vee A_n$ , где каждое $A_n$ — элементарная конъюнкция.

Формула $A$ от $k$ переменных называется совершенной дизъюнктивной нормальной формой { СДНФ } , если:

1. $A$ является ДНФ, в которой каждая элементарная конъюнкция есть конъюнкция $k$ переменных $x_1,x_2,…,x_k$, причем на $i$-м месте этой конъюнкции стоит либо переменная $x_i$ либо ее отрицание;

2. Все элементарные конъюнкции в такой ДНФ попарно различны.

Например: $A = x_1 \wedge$ НЕ $x_2 \vee x_1 \wedge x_2$

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

Она является примером однозначного представления булевой функции в виде формульной { алгебраической } записи.

Теорема о СДНФ: Пусть $f(x_1 x_2, …, x_n)$ – булева функция от n переменных, не равная тождественно нулю. Тогда существует совершенная дизъюнктивная нормальная форма, выражающая функцию $f$.

• В таблице истинности отмечаем наборы переменных, на которых значение функции $f = 1$.
• Записываем для каждого отмеченного набора конъюнкцию всех переменных следующим образом: если значение некоторой переменной в этом наборе равно 1, то в конъюнкцию включаем саму переменную, в противном случае – ее отрицание.
• Все полученные конъюнкции связываем операциями дизъюнкции.

Далее:

Линейный интеграл и циркуляция векторного поля

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

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

Определение двойного интеграла

Поток жидкости через поверхность

Свойства потока векторного поля

Класс M. Теорема о замкнутости класса M

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

Односторонние и двусторонние поверхности. Ориентация поверхности

Поверхностный интеграл первого рода и его свойства

Вычисление тройного интеграла. Теорема о переходе от тройного интеграла к повторному

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

Теорема Стокса

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

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

Обозначения

Наиболее часто встречаются следующие обозначения для операции конъюнкции:

a∧b,a&&b,a&b,a⋅b,aANDb,min(a,b){\displaystyle a\land b,\quad a\And \And b,\quad a\And b,\quad a\cdot b,\quad a\,\,\mathrm {AND} \,\,b,\quad \min(a,b)}

(в случае использования точки как знака логического умножения этот знак — как и при обычном умножении в алгебре — может быть опущен: ab{\displaystyle ab}).

При этом обозначение a∧b{\displaystyle a\land b} наиболее широко распространено в современной математике и математической логике, где оно, впрочем, конкурирует со знаком амперсанда &; последний, появившись ещё в I веке до н. э. как графическое сокращение (лигатура) латинского союза et ‘и’, уже Якобом и Иоганном Бернулли в 1685 году использовался в качестве логической связки (у них он, однако, связывал не высказывания, а понятия). Джордж Буль (а за ним — и другие пионеры систематического применения символического метода к логике: У. С. Джевонс, Э. Шрёдер, П. С. Порецкий) обозначал конъюнкцию знаком ⋅{\displaystyle \cdot } — как обычное умножение. Символ ⋀ (перевёрнутый знак дизъюнкции) в качестве обозначения конъюнкции был предложен Арендом Гейтингом (1930).

Обозначение для конъюнкции было использовано и в раннем языке программирования Алгол 60. Однако из-за отсутствия соответствующего символа в стандартных наборах символов (например, в ASCII или EBCDIC), применявшихся на большинстве компьютеров, в получивших наибольшее распространение языках программирования были предусмотрены иные обозначения для конъюнкции. Так, в Фортране IV и PL/I применялись соответственно обозначения и (с возможностью замены последнего на ключевое слово ); в языках Паскаль и Ада используется зарезервированное слово ; в языках C и C++ применяются обозначения для побитовой конъюнкции и для логической конъюнкции).

Наконец, при естественном упорядочении значений истинности двузначной логики (когда полагают, что <1{\displaystyle 0<1}), оказывается, что (a∧b)=min(a,b).{\displaystyle (a\land b)\,=\,\min(a,b).} Таким образом, конъюнкция оказывается частным случаем операции вычисления минимума; это открывает наиболее естественный способ определить операцию конъюнкции в системах многозначной логики (хотя иногда рассматривают и другие способы обобщения конъюнкции — например, такой: (a∧b)=ab(mod⁡k){\displaystyle (a\land b)\,=\,ab\;(\operatorname {mod} k)} в случае k-значной логики, в которой множество значений истинности представлено начальным отрезком {,…,k−1}{\displaystyle \{0,\dots ,k-1\}} полугруппы N{\displaystyle \mathbb {N} } натуральных чисел).

Таблицы истинности для основных двоичных логических функций

В программировании:

• Конъюнкция = AND = И = ∧{\displaystyle \land } = &
• Дизъюнкция = OR = ИЛИ = ∨{\displaystyle \lor } = |
• Сложение по модулю 2 = XOR = ИСКЛЮЧАЮЩЕЕ ИЛИ = ⊕{\displaystyle \oplus } = ~
• Отрицание = NOT = НЕ = ¬{\displaystyle \neg } = !

Программирование

В компьютерных языках используется два основных варианта конъюнкции: логическое «И» и побитовое (поразрядное) «И». Например, в языках C/C++ логическое «И» обозначается символом «&&», а побитовое — символом «&». В терминологии, используемой в C#, операцию «&» принято называть логическим «И», а операцию «&&» — условным «И», поскольку значения операндов являются условиями для продолжения вычисления. В языках Pascal/Delphi оба вида конъюнкции обозначаются с использованием ключевого слова «and», а результат действия определяется типом операндов. Если операнды имеют логический тип (например, Boolean) — выполняется логическая операция, если целочисленный (например, Byte) — поразрядная.

Логическое «И» применяется в операторах условного перехода или в аналогичных случаях, когда требуется получение результата false{\displaystyle false} или true{\displaystyle true}. Например:

if (a & b & c) 
{
    /* какие-то действия */
};

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

a = false; b = true; c = true;
if (a && b && c) 
{
    /* какие-то действия */ 
};

Проверка истинности выражения в данном случае остановится после проверки переменной a, так как дальнейшее сравнение не имеет смысла.

Результат будет равен true{\displaystyle true}, если оба операнда равны true{\displaystyle true} (для числовых типов не равны {\displaystyle 0}). В любом другом случае результат будет равен false{\displaystyle false}.

При этом применяется стандартное соглашение: если значение левого операнда равно false{\displaystyle false}, то значение правого операнда не вычисляется (вместо b{\displaystyle b} может стоять сложная формула). Такое соглашение ускоряет исполнение программы и служит полезным приемом в некоторых случаях. Компилятор Delphi поддерживает специальную директиву, включающую

{$B-}

или выключающую

{$B+}

подобное поведение. Например, если левый операнд проверяет возможность вычисления правого операнда:

if (a !=  && b  a > 3) 
{
    /* какие-то действия */
};

В этом примере, благодаря проверке в левом операнде, в правом операнде никогда не произойдет деления на ноль.

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

Алгебраические преобразования логических выражений

Любое логическое выражение, как и его переменные (утверждения), принимают два значения: ложь или истина. Ложь обозначается нулём, а истина — единицей. Разобравшись с областью определения и областью допустимых значений, мы можем рассмотреть действия алгебры логики.

Отрицание

Отрицание и инверсия — самое простое логическое преобразование. Ему соответствует частица «не.» Это преобразование просто меняет утверждение на противоположное. Соответственно, значение утверждения тоже меняется на противоположное. Если утверждение А истинно, то «не А» — ложно. Например, утверждение «прямой угол — это угол, равный девяносто градусов» — истина. Тогда его отрицание «прямой угол не равен девяноста градусам» — ложь.

Таблица истинности для отрицания будет такова:

Конъюнкция

Конъюнкция аналогична умножению и соответствует союзу «и». Такое выражение будет верно, только если верны все утверждения, объединённые конъюнкцией. То есть, утверждение «А и Б» будет истинным, только если А — истина и Б — истина. Во всех остальных случаях выражение «А и Б» ложно. Например, высказывание «Земля круглая и плоская» будет ложно, так как первая часть истина, а вторая — ложь.

Таблица истинности конъюнкции

Дизъюнкция

Эта операция может быть обычной или строгой, их результаты будут различаться.

Обычная дизъюнкция или логическое сложение соответствует союзу «или». Она будет истинной если хотя бы одно из утверждений, входящих в неё — истина. Например, выражение «Земля круглая или стоит на трёх китах» будет истинным, так как первое утверждение — истинно, хоть второе и ложно.В таблице это будет выглядеть так:

Строгую дизъюнкцию или сложение по модулю также называют «исключающим или». Эта операция может принимать вид грамматической конструкции «одно из двух: либо …, либо …». Здесь значение логического выражения будет ложным, если все утверждения, входящие в него, имеют одинаковую истинность. То есть, оба утверждения либо вместе истинны, либо вместе ложны.

Таблица значений исключающего или

Импликация и эквивалентность

Импликация представляет собой следствие и грамматически может быть выражена как «из А следует Б». Здесь утверждение А будет называться предпосылкой, а Б — следствием. Импликация может быть ложной, только в одном случае: если предпосылка истинна, а следствие ложно. То есть, ложь не может следовать из истины. Во всех остальных случаях импликация истинна. Варианты, когда оба утверждения имеют одинаковую истинность, вопросов не вызывают. Но почему верное следствие из неверной предпосылки — истина? Дело в том, что из ложной предпосылки может следовать что угодно. Это и отличает импликацию от эквивалентности.

В математике (и других доказательных дисциплинах) импликация используется для указания необходимого условия. Например, утверждение А — «точка О — экстремум непрерывной функции», утверждение Б — «производная непрерывной функции в точке О обращается в ноль». Если О, действительно, точка экстремума непрерывной функции, то производная в этой точке будет, и вправду, равна нулю. Если же О не является точкой экстремума, то производная в этой точке может быть нулевой, а может не быть. То есть Б необходимо для А, но не достаточно.

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

Логическая операция эквивалентность, по сути, является взаимной импликацией. «А эквивалентно Б» означает, что «из А следует Б» и «из Б следует А» одновременно. Эквивалентность верна, когда оба утверждения либо одновременно верные, либо одновременно неверные.

В математике эквивалентность используется для определения необходимого и достаточного условия. Например, утверждение А — «Точка О является точкой экстремума непрерывной функции», утверждение Б — «В точке О производная функции обращается в ноль и меняет знак». Эти два утверждения эквивалентны. Б содержит необходимое и достаточное условие для А

Обратите внимание, что в данном примере утверждений Б на самом деле является конъюнкцией двух других: «производная в точке О обращается в ноль» и «производная в точке О меняет знак»

Прочие логические функции

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

• Штрих Шеффера или несовместимость представляет собой отрицание конъюнкции А и Б
• Стрелка Пирса представляет сбой отрицание дизъюнкции.

Булева алгебра

Определение.
Логическая функция MIN в двухзначной (двоичной) логике называется конъюнкция (логи́ческое «И», логи́ческое умноже́ние или просто «И»).

Правило: результат равен наименьшему операнду.

Описание.
В булевой алгебре конъюнкция — это функция двух, трёх или более переменных (они же — операнды операции, они же — аргументы функции). Переменные могут принимать значения из множества {,1}{\displaystyle \{0,1\}}. Результат также принадлежит множеству {,1}{\displaystyle \{0,1\}}. Вычисление результата производится по простому правилу, либо по таблице истинности. Вместо значений ,1{\displaystyle 0,1} может использоваться любая другая пара подходящих символов, например false,true{\displaystyle false,true} или F,T{\displaystyle F,T} или «ложь», «истина», но при таком обозначении необходимо дополнительно доопределять старшинство, например, true>false{\displaystyle true>false}, при цифровом обозначении старшинство естественно 1>{\displaystyle 1>0}.
Правило: результат равен 1{\displaystyle 1}, если все операнды равны 1{\displaystyle 1}; во всех остальных случаях результат равен {\displaystyle 0}.

Таблицы истинности:
для бинарной конъюнкции

для тернарной конъюнкции

Конъюнкция коммутативна, ассоциативна и дистрибутивна по отношению к слабой дизъюнкции.