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

1. Коммутативность: x∘y=y∘x,∘∈{∧,∨,⊕,∼,∣,↓}{\displaystyle x\circ y=y\circ x,\circ \in \{\land ,\lor ,\oplus ,\sim ,\mid ,\downarrow \}}.
2. Идемпотентность: x∘x=x,∘∈{∧,∨}{\displaystyle x\circ x=x,\circ \in \{\land ,\lor \}}.
3. Ассоциативность: (x∘y)∘z=x∘(y∘z),∘∈{∧,∨,⊕,∼}{\displaystyle (x\circ y)\circ z=x\circ (y\circ z),\circ \in \{\land ,\lor ,\oplus ,\sim \}}.
4. Дистрибутивность конъюнкций и дизъюнкции относительно дизъюнкции, конъюнкции и суммы по модулю два соответственно:
   • x∧(y∨z)=(x∧y)∨(x∧z){\displaystyle x\land (y\lor z)=(x\land y)\lor (x\land z)},
   • x∨(y∧z)=(x∨y)∧(x∨z){\displaystyle x\lor (y\land z)=(x\lor y)\land (x\lor z)},
   • x∧(y⊕z)=(x∧y)⊕(x∧z){\displaystyle x\land (y\oplus z)=(x\land y)\oplus (x\land z)}.
5. Законы де Мо́ргана:
   • x∧y¯=x¯∨y¯{\displaystyle {\overline {x\land y}}={\bar {x}}\lor {\bar {y}}},
   • x∨y¯=x¯∧y¯{\displaystyle {\overline {x\lor y}}={\bar {x}}\land {\bar {y}}}.
6. Законы поглощения:
   • x∧(x∨y)=x{\displaystyle x\land (x\lor y)=x},
   • x∨(x∧y)=x{\displaystyle x\lor (x\land y)=x}.
7. Другие (1):
   • x∧x¯=x∧=x⊕x={\displaystyle x\land {\bar {x}}=x\land 0=x\oplus x=0}.
   • x∨x¯=x∨1=x∼x=x→x=1{\displaystyle x\lor {\bar {x}}=x\lor 1=x\sim x=x\rightarrow x=1}.
   • x∨x=x∧x=x∧1=x∨=x⊕=x{\displaystyle x\lor x=x\land x=x\land 1=x\lor 0=x\oplus 0=x}.
   • x⊕1=x→=x∼=x∣x=x↓x=x¯{\displaystyle x\oplus 1=x\rightarrow 0=x\sim 0=x\mid x=x\downarrow x={\bar {x}}}.
   • x¯¯=x{\displaystyle {\bar {\bar {x}}}=x}, инволютивность отрицания, закон снятия двойного отрицания.
8. Другие (2):
   • x⊕y=x∧y¯∨x¯∧y=(x∨y)∧(x¯∨y¯){\displaystyle x\oplus y=x\land {\bar {y}}\lor {\bar {x}}\land y=(x\lor y)\land ({\bar {x}}\lor {\bar {y}})}.
   • x∼y=x⊕y¯=1⊕x⊕y=x∧y∨x¯∧y¯=(x∨y¯)∧(x¯∨y){\displaystyle x\sim y={\overline {x\oplus y}}=1\oplus x\oplus y=x\land y\lor {\bar {x}}\land {\bar {y}}=(x\lor {\bar {y}})\land ({\bar {x}}\lor y)}.
   • x→y=x¯∨y=x∧y⊕x⊕1{\displaystyle x\rightarrow y={\bar {x}}\lor y=x\land y\oplus x\oplus 1}.
   • x∨y=x⊕y⊕x∧y{\displaystyle x\lor y=x\oplus y\oplus x\land y}.
9. Другие (3) (Дополнение законов де Мо́ргана):
   • x∣y=x∧y¯=x¯∨y¯{\displaystyle x\mid y={\overline {x\land y}}={\bar {x}}\lor {\bar {y}}}.
   • x↓y=x∨y¯=x¯∧y¯{\displaystyle x\downarrow y={\overline {x\lor y}}={\bar {x}}\land {\bar {y}}}.

Существуют методы упрощения логической функции: например, Карта Карно, метод Куайна - Мак-Класки

Правило де Моргана

Законы
де Моргана
(правила
де Моргана
) — логические правила,
связывающие пары дуальных логических
операторов при помощи логического
отрицания.

История
и определение

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

not
(P and Q) = (not P) or (not Q)

not
(P or Q) = (not P) and (not Q)

Обычная
запись этих законов в формальной логике:

в
теории множеств:

Формулы
де-Моргана применимы при любом числе
аргументов. Они иллюстрируют глубокую
взаимную симметрию операций И и ИЛИ:
если операция И избирательно реагирует
на совпадение прямых сигналов, то
операция ИЛИ так же избирательно
реагирует на совпадение их инверсий.
Элемент ИЛИ прозрачен для любого сигнала,
элемент И — для любой инверсии. Пользуясь
формулами де-Моргана, можно легко
переводить логические схемы из базиса
НЕ, И, ИЛИ, в котором человеку привычнее
всего мыслить и составлять исходные
логические выражения, в инвертирующие
базисы, которые эффективнее всего
реализуются интегральной технологией.

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

Примеры задач с решениями по этой теме Пройти тестирование по теме Контрольная по теме

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

Логическое выражение — составные высказывания в виде формулы.

Равносильные логические выражения – логические выражения, у которых последние столбцы таблиц истинности совпадают. Для обозначения равносильности используется знак «=».

Алгоритм построения  таблицы  истинности:

1.подсчитать количество переменных n в логическом выражении;

2. определить число строк в таблице по формуле m=2n, где n — количество переменных;

3. подсчитать количество логических операций в формуле;

4. установить последовательность выполнения логических операций с учетом скобок и приоритетов;

5. определить количество столбцов: число переменных + число операций;

6. выписать наборы входных переменных;

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

Заполнение таблицы:

1.разделить колонку значений первой переменной пополам и заполнить верхнюю часть «0», а нижнюю «1»;

2.разделить колонку  значений  второй переменной на четыре части и заполнить каждую четверть чередующимися группами «0» и «1», начиная с группы «0»;

3.продолжать деление колонок значений последующих переменных на 8, 16 и т.д. частей и заполнение их группами «0» или «1» до тех пор, пока группы «0» и «1» не будут состоять из одного символа.

Пример 1. Для формулы  A/\ (B \/ ¬B /\¬C) постройте  таблицу истинности.

 Количество логических переменных 3, следовательно, количество строк — 23 = 8.

Количество логических операций в формуле 5, количество логических переменных 3, следовательно количество столбцов — 3 + 5 = 8.

 

Пример 2. Определите истинность  логического выражения  F(А, В) = (А\/ В)/\(¬А\/¬В) .

1. В выражении две переменные А и В (n=2).

2.  m_строк=2n, m=22=4 строки.

3. В формуле 5 логических операций.

4. Расставляем порядок действий

1) А\/ В;  2) ¬А;  3) ¬В;  4) ¬А\/¬В;  5) (А\/ В)/\(¬А\/¬В).

5. К_{столбцов}=n+5=2+5=7 столбцов.

А	В	А\/ В	¬А	¬В	¬А\/¬В	F
1	1	1
1	1	1	1	1
1	1	1	1	1
1	1	1

 Вывод: логическое выражение принимает значение истина при наборах F(0,1)=1 и F(1,0)=1.

Пример 3. Построёте таблицу истинности для логического выражения

F = (A\/ B) /\ ¬С

1. В данной функции три логические переменные – А, В, С
2. количество строк таблицы = 23 =8
3. В формуле 3 логические операции.
4. Расставляем порядок действий

1) А\/ В;  2) ¬С; 3) (AVB) /\ ¬С  .

1. количество столбцов таблицы = 3 + 3 = 6

А	В	С	A\/B	¬С	(A\/B) /\ ¬С
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

Пример 4.  Определите истинность формулы: F = ((С \/В) =>  В) /\ (А /\ В) => В.

Построим таблицу истинности этой формулы.

 

Ответ: формула является тождественно истинной.

Пример 5. Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z.

Дан фрагмент таблицы истинности выражения F:

X	Y	Z	F
1
1
1	1

Какое выражение соответствует F?

 1) ¬X/\¬Y/\Z                      2) ¬X\/¬Y\/Z                  3) X\/Y\/¬Z              4) X\/Y\/Z

 Решение (вариант 1, через таблицы истинности):

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

X	Y	Z	F	¬X	¬Y	¬Z	¬X/\¬Y/\Z	¬X\/¬Y\/Z	X\/Y\/¬Z	X\/Y\/Z
1	1	1	1	1	1
1	1	1	1	1	1
1	1	1	1	1	1	1

 Очевидно, что значения заданной функции F совпадают со значениями выражения X\/Y\/¬Z. Следовательно, правильный ответ – 3.

Ответ: 3

 Решение (Вариант 2):

Чтобы не строить таблицу истинности для каждого выражения, можно просто перепроверить предложенные ответы по заданной таблице истинности. Т.е. в каждую из четырех предложенных функций последовательно подставлять значения переменных X, Y  и Z, из заданной таблицы истинности и вычислять значения логического выражения. Если значения вычисляемого выражения совпадут со значением F во всех трех строчках заданной таблицы, то это и есть искомое выражение.

 Рассмотрим данный конкретный пример:

1)первое заданное выражение  ¬X/\¬Y/\Z = 0 при X=0, Y=0, Z=0, что не соответствует первой строке таблицы;

2)второе заданное выражение ¬X\/¬Y\/Z = 1 при X=0, Y=0, Z=1, что не соответствует  второй строке таблицы;

3)третье выражение   X\/Y\/¬Z    соответствует F при всех предложенных комбинациях X,Y и Z;

4)четвертое выражение X\/Y\/Z = 1 при X=0, Y=0, Z=1, что не соответствует второй строке таблицы.

Ответ: 3

10.Стрелка Пирса

Стрелка
Пирса (логическое «ИЛИ-НЕ»)
высказываний a
и b
—
это новое высказывание, которое будет
истинно тогда и только тогда, когда оба
высказывания ложны.

Знаком
стрелки Пирса является ↓

Значения
функции стрелки
Пирса
представлены
в таблице:

Логическим
элементом операции стрелки
Пирса
является:

Стре́лка
Пи́рса
— бинарная логическая
операция, булева
функция над
двумя переменными. Введена в
рассмотрение Чарльзом
Пирсом (Сharles
Peirce) в 1880-1881 г.г.

Стрелка
Пирса, обычно обозначаемая ↓, эквивалентна
операции ИЛИ-НЕ и задаётся следующей
таблицей истинности:

Таким
образом, высказывание «X ↓ Y» означает
«ни X, ни Y». От перемены мест операндов
результат операции не изменяется.

		X ↓ Y

11.
Штрих Ше́ффера
— бинарнаялогическая
операция,булева
функциянад двумя переменными.
Введена в рассмотрениеГенри
Шефферомв 1913 г. (вотдельных
источниках именуется как Пунктир
Чулкова) Штрих Шеффера, обычно обозначаемый
|, эквивалентен операции И-НЕ и задаётся
следующей таблицей истинности:

Таким
образом, высказывание X | Y означает, что
X и Y несовместны, т.е. не являются истинными
одновременно. От перемены мест операндов
результат операции не изменяется.
Штрих Шеффера,
как и стрелка
Пирса,
образует базис для пространства булевых
функций от двух переменных. То есть
используя только штрих Шеффера можно
построить остальные операции. Например,

-отрицание

Дизъюнкция

Конъюнкция

Константа
1

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

Элемент
2И-НЕ (2-in NAND), реализующий штрих Шеффера
обозначается следующим образом (по
стандартам ANSI):

В
европейских стандартах принято другое
обозначение:

12. Диодные
ключи.

Общие сведения. Электронный ключ — это
устройство, которое может находиться
в одном из двух устойчивых состояний:
замкнутом или разомкнутом. Основу
электронного ключа составляет нелинейный
активный элемент (полупроводниковый
диод, транзистор, тиристор и др.),
работающий в ключевом режиме. По типу
используемого нелинейного элемента
электронные ключи делятся на диодные,
транзисторные, тиристорные и т. д.

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

При
положительном входном напряжении диод
открыт и ток через него

,
где —
прямое сопротивление диода.

Выходное
напряжение

.

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

,

где —
обратное сопротивление диода.

При
этом выходное напряжение

.
Как правило, и.
При изменении полярности включения
диода график функцииповернется
на уголвокруг
начала координат.

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

Говоря
о диодных ключах нельзя не упомянуть
особый класс полупроводниковых диодов
— p-i-n-диоды. Они применяются только для
коммутации ВЧ и СВЧ сигналов. Это возможно
благодаря их уникальному свойству —
регулируемой проводимости на частоте
сигнала. Такое регулирование осуществляется
обычно либо при подаче на диод внешнего
постоянного напряжения смещения, либо
непосредственно уровнем сигнала (для
ограничительных p-i-n-диодов).

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

Построение формулы логической функции по таблице истинности

Строится формула следующим образом:

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

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

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

Задача: Дана полная таблица истинности некоторой функции. Построить формулу функции по этой таблице.

\( x \)	\( y \)	\( z \)	\( F \)
1
1	1
1	1
1	1
1	1	1
1	1
1	1	1	1

 1. Удаляем строки со значением функции равным 0

\( x \)	\( y \)	\( z \)	\( F \)
1	1
1	1
1	1	1
1	1	1	1

2. Составляем конъюнкции для каждой строки

\( x \)	\( y \)	\( z \)	\( F \)	Конъюнкция
1	1	\( \overline{x} ⋅ y ⋅ \overline{z} \)
1	1	\( x ⋅ \overline{y} ⋅ \overline{z} \)
1	1	1	\( x ⋅ \overline{y} ⋅ z \)
1	1	1	1	\( x ⋅ y ⋅ z \)

3. Объединяем все конъюнкции дизъюнкцией:

\( F(x,y,z) = \overline{x} ⋅ y ⋅ \overline{z} + x ⋅ \overline{y} ⋅ \overline{z} + x ⋅ \overline{y} ⋅ z + x ⋅ y ⋅ z \)

Логика по Аристотелю

Древние греки вообще любили рассуждать о том, как устроен наш мир и в чём его смысл. У них это, кстати, получалось вполне неплохо. Так, учёный и философ Левкипп и его ученик Демокрит открыли атомы, не имея при этом наших микроскопов. Сделать это им удалось в том числе благодаря логике.

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

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

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

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

Коммутативность конъюнкции и коммутативность дизъюнкции

Коммутативность – это перестановочность:

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

И, кроме того, здесь я снова хочу подчеркнуть формализм математической логики. Так, например, фразы «Студент сдал экзамен и выпил» и «Студент выпил и сдал экзамен» различны с содержательной точки зрения, но неразличимы с позиций формальной истинности. …Таких студентов знает каждый из нас, и из этических соображений мы не будет озвучивать конкретных имён =)

Ассоциативность логического умножения и сложения

Дистрибутивные свойства

Обратите внимание, что во 2-м случае будет некорректно говорить о «раскрытии скобок», в известном смысле здесь «фикция» – ведь их можно убрать вообще: , т.к. умножение – это более сильная операция

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

Закон идемпотентности

Что делать, латынь….

Прямо какой-то принцип здоровой психики: «я и я – это я», «я или я – это тоже я» =)

И тут же несколько похожих тождеств:

…мда, что-то я даже подзавис… так и доктором философии завтра можно проснуться =)

Закон двойного отрицания

Ну а здесь уже напрашивается пример с русским языком – все прекрасно знают, что две частицы «не» означают «да». А для того, чтобы усилить эмоциональную окраску отрицания нередко используют три «не»: – даже с крохотным доказательством получилось!

 – «а был ли мальчик?» =)

В правом тождестве скобки можно опустить.

Законы де Моргана

Предположим, что строгий Преподаватель (имя которого вам тоже известно:)) ставит экзамен, если  – Студент ответил на 1-й вопрос и  – Студент ответил на 2-й вопрос. Тогда высказывание , гласящее о том, что Студент не сдал экзамен, будет равносильно утверждению  – Студент не ответил на 1-й вопрос или на 2-й вопрос.

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

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

Да, это доказательство является примитивным (а кто-то скажет, что и «тупым»), но типичный Преподаватель по матлогике вытрясет за него душу. Поэтому даже к таким простым вещам не стОит относиться пренебрежительно.

Теперь убедимся, например, в справедливости закона де Моргана .

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

Любую равносильность  можно представить в виде тождественно истинной формулы . Это значит, что ПРИ ЛЮБОМ исходном наборе нулей и единиц «на выходе» получается строго единица. И этому есть очень простое объяснение: так как таблицы истинности  и  совпадают, то, разумеется, они эквивалентны. Соединим, например, эквиваленцией левую и правую часть только что доказанного тождества де Моргана:
Или, если компактнее:

Задание 2

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

а) ;

б)

Краткое решение в конце урока. Не ленимся! Постарайтесь не просто составить таблицы истинности, но ещё и чётко сформулировать выводы. Как я недавно отмечал, пренебрежение простыми вещами может обойтись очень и очень дорого!

Построение таблиц истинности для логических выражений

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

Для того, чтобы построить таблицу истинности выражения нужно:

• Определить количество переменных, участвующих в выражении
• Определить количество составляющих выражение логических операций
• Заполнить строки таблицы всеми возможными наборами значений переменных. Наборы значений лучше представлять в виде двоичных чисел. Например, для трех переменных нужно заполнить восемь строк с 000 до 111.
• Вычислить и заполнить промежуточные операции в таблице
• Вычислить и заполнить значение логического выражения

Задача: Построить таблицу истинности для логического выражения \(  \overline{x} ⋅ y  + \overline{x + y} \)

Решение: 

Переменные	Промежуточные операции	Значение выражения
\( x \)	\( y \)	\( \overline{x} \)	\( \overline{x} ⋅ y \)	\( x + y \)	\( \overline{x + y} \)	\( \overline{x} ⋅ y  + \overline{x + y} \)
1	1	1
1	1	1	1	1
1	1
1	1	1

Четвёртый закон логики: закон достаточного основания

Любое суждение должно быть обосновано. Для появления следствия должна быть достаточная причина.

— Аристотель

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

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

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

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

Продолжаем знакомиться с законами логики!

Да, совершенно верно – мы с ними уже вовсю работаем:

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

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

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

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

Доказательство тривиально:
«На выходе» получены исключительно нули, следовательно, формула действительно тождественна ложна.

Однако и любое противоречие – это тоже закон логики, в частности:

Нельзя объять столь обширную тему в одной-единственной статье, и поэтому я ограничусь ещё лишь несколькими законами:

Закон исключённого третьего

  – в классической логике любое высказывание истинно или ложно и третьего не дано. «Быть или не быть» – вот в чём вопрос.

Самостоятельно составьте табличку истинности и убедитесь в том, что это тождественно истинная формула.

Закон контрапозиции

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

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

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

И снова вернёмся к нашим содержательным примерам: для высказываний   – число делится на 4,  – число делится на 2 справедливы прямая и противоположная теоремы, но ложны обратная и противоположная обратной теоремы. Для «взрослой» же формулировки теоремы Пифагора истинны все 4 «направления».

Закон силлогизма

Тоже классика жанра: «Все дубы – деревья, все деревья – растения, следовательно, все дубы – растения».

Ну и здесь опять хочется отметить формализм математической логики: если наш строгий Преподаватель думает, что некий Студент – есть дуб, то с формальной точки зрения данный Студент, безусловно, растение =) …хотя, если задуматься, то может быть и с неформальной тоже =)

Давайте на этой веселой ноте проведём доказательство. В данную формулу входят уже  элементарных высказывания , а значит, всего будет:  различных  комбинаций нулей и единиц (см. три левых столбца таблицы). Заодно, кстати, записал вам общую формулу; с точки зрения комбинаторики, здесь размещения с повторениями.

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

1) выполняем импликации  и . Вообще говоря, можно сразу выполнить и 3-ю импликацию, но с ней удобнее (и допустимо!) разобраться чуть позже;

2) к столбцам  применяем правило И;

3) вот теперь выполняем ;

4) и на завершающем шаге применяем импликацию к столбцам  и .

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

Задание 3

Выяснить, будет ли являться законом логики следующая формула:

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