Основные законы логической алгебры

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

Существует три способа представления выражений:

• в виде таблицы истинности;
• аналитическая форма;
• логическая форма.

Таблица истинности 

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

Пример

Аналитическое выражение

Рассмотрение данной формы невозможно без введения новых понятий.

• терм – компонент выражения;
• ранг терма – число переменных в терме;
• дизъюнктивный терм (макстерм) – логическое сложение произвольного количества попарно независимых переменных;
• конъюнктивный терм (минтерм) – логическое умножение произвольного количества попарно независимых переменных. 

В аналитической записи используют две формы выражения:

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

\(f(a,b,c)=\overline ab\overline c+a\overline b+a\overline c+b\)

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

\(f(X_1X_2X_3X_4)=(X_1+\overline{X_2}+X_3)(\overline{X_1}+\overline{X_2}+X_3+X_4)(X_1+X_2)\)

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

Совершенная дизъюнктивная форма (дизъюнкция конституент единицы) записывается так:

\(F(a,b,c)=\overline abc+abc+abc+ab\overline c\)

Совершенная конъюнктивная форма (конъюнкция конституент нуля) имеет вид:

\(F(a,b,c,d)=(a+b+\overline c+d)(\overline a+b+\overline c+d)(\overline a+\overline d+\overline c+d)\)

Аналитические формы полностью дуальны.

Числовая запись

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

Вид для совершенной дизъюнктивной нормальной формы:

\(f(a,b,c)=\vee(1,3,6,7)\)

Вид для совершенной конъюнктивной нормальной формы:

\(f(a,b,c)=\wedge(0,2,4,5)\)

Законы логических операций

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

1. Закон противоречия говорит о том, что никакое предложение не может быть истинно одновременно со своим отрицанием. «это яблоко спелое» и «это яблоко неспелое».

2. Закон исключенного третьего говорит о том, что для каждого высказывания имеются лишь две возможности: это высказывание либо истинно, либо ложно. Третьего не дано. «Сегодня я либо получу 5, либо не получу». Истинно либо суждение, либо его отрицание.

3. Закон двойного отрицания заключается в том, что отрицать отрицание какого-нибудь высказывания — то же, что утверждать это высказывание.

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

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

   коммутативность:

   ассоциативность:

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

7. Законы поглощения констант утверждают, что ложь не влияет на значение логического выражения при дизъюнкции, а истина — при конъюнкции.

8. Законы поглощения показывают как упрощать логические выражения при повторе операнда.

9. Законы де Мо́ргана (правила де Мо́ргана) — логические правила, связывающие пары логических операций при помощи логического отрицания. Названы в честь шотландского математика Огастеса де Моргана. В краткой форме звучат так:

   Отрицание конъюнкции есть не что иное, как дизъюнкция отрицаний.

   Отрицание дизъюнкции есть не что иное, как конъюнкция отрицаний.

Вопросы и задачи

1. Упростите выражение: (X /\ Y) → ¬Z.
2. Найдите решения выражения: ((X → Y) \/ Z) X.
3. Определите истинность выражения: (Z \/ X) → (Y /\ X).
4. Определите истинность выражения: ((C \/ B)→B) /\ (A /\ B))→B.
5. Упростите выражение: A \/ B \/ (¬A \/ B) \/ C /\ D.
6. Упростите выражение: (A \/ B) /\ (A \/ B \/ C).
7. Решить в Excel выражение (без его преобразований): F = ¬X /\ ¬Y \/ Z \/ X /\ Y.
8. Для какого из названий животных ложно высказывание: ((Заканчивается на согласную букву) /\ (В слове 7 букв) → ¬(Третья буква согласная))?
   1) Верблюд 2) Страус 3) Кенгуру 4) Леопард
9. Какое из приведенных имен удовлетворяет логическому условию((первая буква гласная → вторая буква гласная) /\ последняя буква гласная)?
   1) ИРИНА 2) МАКСИМ 3) АРТЕМ 4) МАРИЯ

10. Упростите выражение: A /\ B \/ A /\ B /\ (C \/ D).

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

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

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

Замечание. Знаки алгебры логики намеренно заменены на сложение и умножение.

№	Для ИЛИ	Для И	Примечание
1	A + 0 = A	A • 1 = A	Ничего не меняется при действии, константы удаляются
2	A + 1 = 1	A • 0 = 0	Удаляются переменные, так как их оценивание не имеет смысла
3	A + B = B + A	AB = BA	Переместительный (коммутативности)
4	A + = 1		Один из операторов всегда 1 (закон исключения третьего)
5		A • = 0	Один из операторов всегда 0 (закон непротиворечия)
6	A + A = A	A • A = A	Идемпотентности (NB! Вместо A можно подставить составное выражение!)
7	¬¬A = A	Двойное отрицание
8	(A+B)+C = A+(B+C)	(A•B)•C = A•(B•C)	Ассоциативный
9	(A+B)•C =  = (A•C)+(B•C)	(A•B)+C =  = (A+C)•(B+C)	Дистрибутивный
10	(A+B)•(¬A+B) = B	(A•B)+(¬A•B) = B	Склеивания
11	¬(A+B) = ¬A•¬B	¬(A•B) = ¬A+¬B	Правило де Моргана
12	A+(A•C) = A	A•(A+C) = A	Поглощение
13	A→B = ¬A+B и A→B = ¬B→¬A	Снятие (замена) импликации
14	1) AB = (A•B)+(¬A•¬B)2) AB = (A + ¬B)•(¬A + B)	Снятие (замена) эквивалентности

Основные операции

Количество логических операций, которыми обычно оперирует логика 6:

• Отрицание.
• Умножение.
• Сложение
• Следование.
• Дизъюнкция.
• Равнозначность.

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

Отрицание или инверсия

Операция отрицания или НЕлогическое, корректнее будет название инверсия.Конечное высказывание будет противоположным первоначальному (исходному). Применяется для одного выражения, которое может быть как сложным, так и элементарным.

На примере этой простейшей операции удобно показывать, насколько лаконичны и информативны таблицы истинности. Обозначим исходное высказывание буквой А, соответственно, окончательное будет не А (или НЕ, ‾, ˥ not А). А их ложность или правдивость напишем при помощи цифр 0 и 1.

Получается, если исходное значение правда, то новое будет ложь, и наоборот.

Умножение или конъюнкция &

Логическое И или умножение еще называют конъюнкцией. Финальное высказывание будет правдивым, только если его составляющие тоже правдивы. Во всех остальных случаях оно будет ложным. Применяется для двух и более аргументов, элементарных или сложных. Обозначение А и В; А ^ В; А &В; A and В.

Как видно, при помощи таблицы истинности из 15 ячеек можно описать то, на описание чего при помощи слов пришлось бы потратить минимум 5 полноценных предложений.

Логическое И в обычной жизни:

• Хорошая певица должна быть талантливой и упорной (наличие только одного качества не позволит проявить миру свой талант).
• По условиям задачи А – число меньше 30, В – число делиться на 3. Нужно найти решение А ˄ В.

Решение: Первое множество содержит числа 1,2,3….29. Второе – 3,6,9,…27. Решением будет множество на пересечении множеств А и В, что хорошо покажут диаграммы Эйлера-Венна. А ˄ В будет истинным для множества чисел 3,6,9,….27.

Сложение или дизъюнкция V

Логическое ИЛИ, сложение по-другому называют дизъюнкцией. Оно истинно всегда, кроме случая, если ложны все составные высказывания. Функция распространяется на простые и сложные исходные аргументы. Обозначение А или В; A v В; А ог В.

В обычной жизни нас окружает логическое ИЛИ:

• «Чтобы сдать тесты на «отлично», нужно старательно готовиться ИЛИ должно повезти с билетом».
• Есть задача с 2-мя условиями: А – число делится на 5, В – число делится на 2.

Решение: Первое множество чисел включает в себя 5, 10, 15…Второе – 10, 20, 30…Решение, при котором истинно Аv В – совокупность обеих множеств (5, 10, 15, 20, 25, 30…).

Следование или импликация

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

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

Логическое следование в обычной жизни:

• Если пойти к врачу, можно выздороветь (но можно выздороветь и без похода к врачу, а можно и после визита в больницу не выздороветь).
• По условию задачи, А – если число делится на 10, то В делится на 5.

Строгая дизъюнкция

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

Это пример исключающей функции. Аналог в словесном выражении – «либо». Разница от простой дизъюнкции в том, что конечное выражение будет истинным, только если будет правдой одна переменная.

Эквиваленция или равнозначность 

Операция, выдающая истину в случае, если обе исходные переменные истины или неправдивы.Обозначают А ~В, А  В.

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

Пример эквивалентности из обычной жизни:

• Если вечером на горизонте солнце темно-красного цвета, значит, завтра будет ветреный день.
• В задаче 2 условия: А – сумма цифр числа равно 9, В – число делится на 9. АВ означает, что число делится на 9, если сумма цифр равна 9.

Алгебра логики и решение задач

Несмотря на то, что логика, как наука о размышлении, существовала еще 5 в. До н.э., теперь это важная часть многих наук, а не только философии и риторики. Также логика существует, как отдельная наука уже более 200 лет.

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

Стоит остановиться на базовых понятиях алгебры логики:

• константы (0,1);
• переменные;
• формула;
• знаки операций;
• скобки.

Логическая переменная – обозначение логического выражения, которое может быть true (t, правда, истина, да, 1) – false (f, ложь, нет, 0).

Формула– символьный способ выражения операции между переменными при помощи специальных знаков и скобок ().

Логическое высказывание – утверждение, в котором говорится только правда или только ложь.

Образец таких предложений: «Луна – вертится вокруг Марса» – ложно, а «После зимы всегда приходит весна» – истинно.

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

Элементарные высказывания – те, к которым нельзя применить понятие истинности или ложности. Их обозначают различными символами (латинские буквы, цифры), знаками. Ими занимаются те сферы, к которым они относятся. Они входят в состав высказываний логики.

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

Чтобы образовать такое составное предложение в обычной жизни, используют связки И, ИЛИ, НЕ. А научный подход заменил их на конъюнкцию, дизъюнкцию, инверсию и более сложные операции. Все эти процессы выражают словесно, таблично (таблицы истинности) или графически (диаграммы Эйлера-Венна).

Простые выражения содержат лишь одно выражение (правдивое или нет), и не содержит никаких логических операций.

Сложные могут содержать от 2 и больше аргументов (простых выражений), которые между собой связаны логическими операциями.

Еще используют понятие «предикат» – содержит любое количество переменных без перечисления всех составляющих данных. Это предикат простых, отрицательных P(x)=(x<0) чисел.

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

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

Формулы логики высказываний

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

В примерах 1 и 2 мы учились записывать с помощью логических операций сложные высказывания.
Вообще-то они называются формулами логики высказываний.

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

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

Для построения формул логики высказываний кроме указанных выше букв используются знаки
логических операций

~, ∧, ∨, →, ,

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

Понятие формулы логики высказываний определим следуюшим
образом:

1) элементарные формулы (атомы) являются формулами логики высказываний;

2) если и —
формулы логики высказываний, то , ,
, ,
тоже являются формулами логики
высказываний;

3) только те выражения являются формулами логики высказываний, для которых это
следует из 1) и 2).

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

Пример 6. Пусть — одиночное
высказывание (атом) «Все рациональные числа являются действительными», —
«Некоторые действительные числа — рациональные числа», —
«некоторые рациональные числа являются действительными». Переведите в форму словесных высказываний
следующие формулы логики высказываний:

1) ;

2) ;

3) ;

4) ;

5) ;

6) .

Решение.

1) «нет действительных чисел, которые являются рациональными»;

2) «если не все рациональные числа являются действительными, то нет рациональных чисел, являющихся действительными»;

3) «если все рациональные числа являются действительными, то некоторые действительные числа — рациональные числа и некоторые рациональные числа являются действительными»;

4) «все действительные числа — рациональные числа и некоторые действительные числа — рациональные числа и некоторые рациональные числа являются действительными числами»;

5) «все рациональные числа являются действительными тогда и только тогда, когда не имеет место быть, что не все рациональные числа являются действительными»;

6) «не имеет места быть, что не имеет место быть, что не все рациональные числа являются действительными и нет действительных чисел, которые являются рациональными или нет рациональных чисел, которые являются действительными».

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

Решение. Составление таблицы истинности начинаем с записи значений («истина» или «ложь»)
для одиночных высказываний (атомов) , и
. Все возможные значения записываются в восемь строк таблицы. Далее,
определяя значения операции импликации, и продвигаясь вправо по таблице, помним, что значение равно «лжи» тогда, когда из «истины» следует «ложь».

И	И	И	И	И	И	И	И
И	И	Л	И	И	И	Л	И
И	Л	И	И	Л	Л	Л	Л
И	Л	Л	И	Л	Л	И	И
Л	И	И	Л	И	Л	И	И
Л	И	Л	Л	И	Л	И	Л
Л	Л	И	И	И	И	И	И
Л	Л	Л	И	И	И	Л	И

Заметим, что никакой атом не имеет вида
, ,
, ,
. Такой вид имеют сложные формулы.

Число скобок в формулах логики высказываний можно уменьшить, если принять, что

1) в сложной формуле будем опускать внешнюю пару скобок;

2) упорядочим знаки логических операций «по старшинству»:

, →, ∨, ∧, ~ .

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

Пример 8. Восстановите скобки в формуле логики высказываний
.

Решение. Скобки восстанавливаются пошагово следующим образом:

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

• Пригодится: минимизация логических функций — общие сведения
• Пригодится: минимизация логических функций методом непосредственных преобразований
• Пригодится: минимизация логических функций методом Квайна

Логические операции

Инверсия (логическое отрицание — НЕ) — обозначение !.

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

Присоединение частицы НЕ к сказуемому простого высказывания A называется операцией логического отрицания.

Результат будет истинным, если исходное высказывание ложно, и наоборот, ложным — если исходное высказывание истинно.

A	!A
1
1

Конъюнкция (логическое умножение — И) – обозначение & или &&

Результат будет истинным тогда и только тогда, когда оба исходных высказывания истинны.

A	B	A & B
1
1
1	1	1

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

Отметим, что для конъюнкции, так же как и для следующей рассматриваемой функции – дизъюнкции – действуют ассоциативный (сочетательный) и коммуникативный (переместительный) законы.

В то же время для некоторых других логических функций тот или иной закон не действует. Некоторые из примеров таких функций мы рассмотрим ниже.

Чем отличается оператор & от &&:

• Оператор & всегда вычисляет оба операнда
• Оператор && вычисляет второй операнд, только если это необходимо.

Дизъюнкция (логическое сложение — ИЛИ) – обозначение | или ||.

Результат будет истинным тогда, когда истинно хотя бы одно из высказываний.

A	B	A | B
1	1
1	1
1	1	1

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

Чем отличается оператор | от ||:

• Оператор | всегда вычисляет оба операнда
• Оператор || вычисляет второй операнд, только если это необходимо.

Электросхемы и таблицы истинности

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

Переменными являются переключатели, а результат (горит лампа/идет ток) будет «1» – истина или «0» – ложь.

Для конъюнкции и инверсии подходит последовательное соединение, но во втором случае переключатель один, для дизъюнкции – параллельное.

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

Диаграммы Эйлера-Венна

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

Число пересечений (областей) можно посчитать сразу, оно равно n = 2N, где N – число множеств. Так как значение двойки в степени растет очень быстро (4,8,16), обычно диаграммы используют для 2-3 множеств. Далее области пересечения будут сливаться, образуя неразличимые участки. Если множеств 2-3, то рисуют круги, если больше 4 – эллипсы. Этот «цветок» помещают в прямоугольную конструкцию, которую называют универсум U (универсальное множество).

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

Конъюнкция множеств А и В:

Отрицание Ā:

Сложное выражение (Ā)∨(A∧B), составленное из элементарных Ā, A∧B и их комбинации, графическое выражение:

Примеры использования диаграмм Эйлера-Венна

Пример №1:

Есть 2 множества цифр и универсум:

А={4,5,6,7}

В={6,7,8,9}

U={0,4,5,6,7,8,9}

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

Заставляем компьютер понимать «если …, то…»

То, что мы называем логическими операциями, впервые появилось предположительно в
Древней Греции для доказательства философских постулатов. А в наше время логические операции наиболее
широко применяются в компьютерной технике. Но при всём этом компьютер «не умеет» выполнять логическую
операцию импликации. Она компьютеру «не понятна». Есть, однако, способ заставить компьютер понимать
условие «если …, то», соответствующее, как известно, импликации. Для этого вместо составного оператора
«если p, то q» нужно использовать составной оператор «не p или q».
То есть, вместо .

Как видно ниже, таблица истинности для такой замещающей логической операции идентична
таблице истинности для импликации.

И	И	И
И	Л	Л
Л	И	И
Л	Л	И

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

;

.

Решение.

Заменяем импликацию между двумя парами скобок, отрицая самый левый знак отрицания:

.

Убираем эквиваленцию между и
и между и :

.

Используя закон де Моргана, немного упрощаем и окончательно получаем:

.

• Пригодится: минимизация логических функций — общие сведения
• Пригодится: минимизация логических функций методом непосредственных преобразований
• Пригодится: минимизация логических функций методом Квайна

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

Имеется большое количество правил в данной сфере деятельности, но сегодня будет рассмотрено несколько основных.

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

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

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

Закон двойственности и инверсии (закон Моргана) — основоположником данного правила стал шотландский математик и логик де Морган. Он разработал правило, которое связывает логические операции конъюкцию (И) и дизъюнкцию (ИЛИ) с помощью отрицания.

Основные законы алгебры логики представлены в таблице:

Применение логики высказываний в информатике и программировании

Логика высказываний применяется в информатике и программировании в виде объявления логических переменных и присвоения им логических значений «ложь» или «истина», от которых зависит ход дальнейшего исполнения программы. В небольших программах, где задействована лишь одна логическая переменная, этой логической переменной часто даётся имя, например, «флаг» («flag») и подразумевается, что «флаг поднят», когда значение этой переменной — «истина» и «флаг опущен», когда значение этой переменной — «ложь». В программах большого объёма, в которых несколько или даже очень много логических переменных, от профессионалов требуется придумывать имена логических переменных, имеющих форму высказываний и смысловую нагрузку, отличающую их от других логических переменных и понятных другим профессионалам, которые будут читать текст этой программы.

Так, может быть объявлена логическая переменная с именем «ПользовательЗарегистрирован» (или его англоязычный аналог), имеющая форму высказывания, которой может быть присвоено логическое значение «истина» при выполнении условий, что данные для регистрации отправлены пользователем и эти данные программой признаны годными. В дальнейших вычислениях значения переменных могут меняться в зависимости от того, какое логическое значение («истина» или «ложь») имеет переменная «ПользовательЗарегистрирован». В других случах переменной, например, с именем «ДоДняХОсталосьБолееТрёхДней», может быть присвоено значение «Истина» до некоторого блока вычислений, а в ходе дальнейшего исполнения программы это значение может сохраняться или меняться на «ложь» и от значения этой переменной зависит ход дальнейшего исполнения программы.

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

• Больше интересных статей читай по хэштегу#article@physics_mathв группеPhysics.Math.Code
• Помощь по физике, математике, программировании, информатике и другим техническим предметам найдете вРепетитор | IT mentor
• Наш канал в telegram (все книги паблика в одном месте):@physics_lib
• Скачать все книги:https://tlgg.ru/physics_libhttps://tgtg.su/physics_libhttps://telete.in/physics_libhttps://ttttt.me/physics_lib

Графическое решение числовых выражений по координатной прямой

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

(X > 2) /\ ¬(X > 5).

Хорошо видно, что выражение берется в скобки для однозначного восприятия. Прежде чем наносить значения на рисунок,
следует избавиться от отрицания.
В этом случае происходит замена знаков отношения на противоположные по схеме:   ≤, =  ≠.

В нашем примере мы получим

(X > 2) /\ (X ≤ 5).

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

Возможные целочисленные ответы — 3, 4, 5.

Логические выражения и операторы

Как вычислить истинность логического выражения?

Термин высказывание, мы теперь знаем. Но что такое логическое выражение? Выражение — это уравнение из высказываний, как математическое уравнение из чисел. 

«Этот кот вооружен и его глаза зеленого цвета», — в одном выражении мы использовали два высказывания. 

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

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

Так и работают логические операторы — в зависимости от них все выражение и принимает значение истины или лжи.

Основные логические операторы алгебры логики:

Конъюнкция: логическое умножение или логическое И. В записи обозначается как ∧. А ∧ В дает истину только в том случае, если оба высказывания А и В истинны.Называется логическим умножением, потому что имеет схожий принцип работы: если хоть один из множителей будет равен 0, все выражение будет равно 0.В примере про кота выше выражение «Этот кот вооружен ∧ его глаза голубые» будет ложным. Он вооружен, но глаза у него не голубые. Одно из высказываний не выполнилось, так что конъюнкция равна 0.

Дизъюнкция: логическое сложение или логическое ИЛИ. В записи обозначается как ∨

А ∨ В дает истину в том случае, если хотя бы одно из высказываний истинно.Называется логическим сложением за схожесть: если складывать только 0 и 1, чем мы и занимаемся, то достаточно одному слагаемому быть 1, чтобы все выражение не было равно 0.Важно сразу понять — если применить логическое сложение к двум единицам (1 ∨ 1), мы получим не 2, а все еще 1. Все-таки единица здесь означает не число, а истину, и сложив две, мы не получим одну сверх-истину.Тогда выражение «Этот кот вооружен ∨ его глаза голубые» будет уже истинным: глаза его не голубые, но он все-таки вооружен

Дизъюнкция вернет нам 1.

Инверсия: логическое отрицание или логическое НЕ. Превращает истину в ложь и наоборот.Ложное высказывание «Его глаза голубые» можно легко превратить в истину, если сказать «Его глаза НЕ голубые». В записи обозначается чертой над выражением или знаком ¬, например, ¬А.

Эквиваленция, если проще — равенство. Если оба высказывания равны (оба 0 или оба 1), то получим истину, иначе — ложь. Обозначается как ≡.Истинным будет выражение «У кота нет оружия так же, как его глаза голубые». И то, и другое — ложь, но мы их сравнили, сказав, что они одинаковы по истинности, что уже правда.

Импликация, иначе говоря, следование. Обозначается стрелочкой, например А ⇒ В. Если из истины следует ложь, то это автоматически ложь, все остальное — истина. Например, вас никто не просил кормить кота. Если вы этого не сделаете, ничего плохого и не случится. А если сделаете — тоже хорошо, кот будет рад. А вот если вас попросили покормить кота, надо обязательно это сделать. Не сделаете — будет плохо.

Приоритет этих операторов:

1. инверсия;
2. конъюнкция;
3. дизъюнкция;
4. импликация;
5. эквиваленция.

Как и везде в математике, приоритет можно менять с помощью скобок — что в них, то выполняется в первую очередь.

Проверь себя

Задание 1.Выберите правильный порядок приоритета логических операторов:

1. Импликация, эквиваленция, конъюнкция, дизъюнкция, инверсия.
2. Инверсия, конъюнкция, дизъюнкция, импликация, эквиваленция.
3. Инверсия, конъюнкция, дизъюнкция, эквиваленция, импликация.
4. Инверсия, дизъюнкция, конъюнкция, эквиваленция, импликация.

Задание 2.Сопоставьте название логического оператора с упрощенным:

Инверсия	А. Умножение
Эквиваленция	Б. Отрицание
Импликация	В. Следование
Дизъюнкция	Г. Равенство
Конъюнкция	Д. Сложение

Задание 3.Чему будет равен последний столбец таблицы истинности для уравнения: А ∨ В ⇒ ¬С?

1. 11101010
2. 11101111
3. 11111110
4. 11000100

Задание 4.Сократите логическое выражение: ¬(А ∨ В) ∧ (¬А ∨ С)

1. ¬(А ∧ В)
2. ¬А ∨ ¬В ∨ С
3. ¬А ∧ ¬В ∧ С
4. ¬А ∧ ¬В

Ответы: 1. — 2; 2. — 1Б, 2Г, 3В, 4Д, 5А; 3. — 1; 4. — 4.

Решение логических выражений

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

Для составления таблиц истинности необходимо:

• определить количество строк в таблице: 2n, n–количество переменных
• определить количество столбцов в таблице: количество логических переменных + количество логических операций
• установить последовательность выполнения логических операций
• построить таблицу, указывая названия столбцов и возможные наборы значений исходных логических переменных
• заполнить таблицу истинности по столбцам

Например, построим таблицу истинности для ассоциативного закона дизьюнкции: А | (В | С)

• количество строк: 23=8
• количество столбцов: 3+2=5

A	B	C	B | C	A | (B | C)
1	1	1
1	1	1
1	1	1	1
1	1
1	1	1	1
1	1	1	1
1	1	1	1	1

КОНТРОЛЬНЫЕ ВОПРОСЫ

Основные алгоритмические конструкции

Языки программирования

Посылки и выводы. Валидный и не валидный аргумент

Пусть есть высказывания, которые можно назвать посылками. Пусть также есть
высказывание, которое можно назвать выводом. Словосочетание «можно назвать» используется при условии,
что посылки связываются с выводом. То есть, из посылок логически следует вывод. Тогда, если посылки имеют значения «истина» и вывод тоже
имеет значение «истина», то аргумент является валидным. Если же посылки имеют значения «истина»,
а вывод имеет значение «ложь», то аргумент не является валидным. Синонимы понятия «валидность» (в
рассматриваемом здесь значении) — «логическая правильность», «резонность».

Пример валидного аргумента:

• Посылка. A и B — программисты
• Посылка. A и B разрабатывают программы для бухгалтеров
• Вывод. Есть программисты, которые разрабатывают программы для бухгалтеров

То есть, из посылок логически следует вывод.

Пример не валидного аргумента:

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

То есть, из посылок логически не следует вывод.

Пример 12. Проверьте валидность аргумента, если

• Посылка.
• Посылка.
• Вывод.

Решение. Составляем таблицу истинности:

И	И	Л	И	И	И
И	Л	Л	Л	Л	И
Л	И	И	И	И	Л
Л	Л	И	И	И	И

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