Бесплатная горячая линия

8 800 301 63 12
Главная - Другое - Основные законы алгебры логики примеры

Основные законы алгебры логики примеры

Основные законы алгебры логики примеры

Алгебра логики: законы алгебры логики


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

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

В обратном случае выражение принимает значение ложного.Главные ее свойства:· При ложности хотя бы одного выражения все сложное выражение будет ложным.· При истинности всех простых выражений сложное выражение является истинным.· Значение сложного выражения независимо от последовательности простых выражений.Данное выражение также называют логическим сложением. Оно истинно почти всегда, за исключением ситуации, когда все подвыражения ложны.Главные тезисы:· В случае, когда хотя бы одно выражение истинно, вся дизъюнкция становится истинной.· В случае, когда все выражения ложны, вся дизъюнкция становится ложной.· Значение дизъюнкции независимо от последовательности простых подвыражений.Инверсия (также называемая логическим отрицанием) заключается в добавлении частицы «не» к выражению.

В случае, когда изначальное выражение истинно, его отрицание – ложь.

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

Она является истинной на равных наборах значений переменных.Не каждый студент может себе позволить за семестр в ВУЗе отдать100 000 ₽. Но круто, что естьна учебу.–этовозможность учиться на желанной специальности.каждый получит бонус от300 ₽до100 000 ₽–Выражение также называют сложением по модулю. Оно истинно только в случае, при котором значения аргументов не являются равными.

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

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

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

Ну или просто сэкономить на учебе. Ты точно получишьот300 ₽до100 000 ₽,перейдя по ссылке!

Алгебра логики. Основные логические операции и их таблицы истинности.

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

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

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

Сама алгебра логики изучает свойства функций, у которых значения как аргументов, так и самих функций ограничены двумя значениями, например, \(\{0,1\}\). Отцом алгебры логики считается английский математик Джордж Буль (1815-1864), поэтому алгебру логики иногда называют булевой алгеброй. Долгое время алгебра логики была известна лишь узкому кругу специалистов, и только в 1938 году американский математик Клод Шеннон (1916-2001), стоявший у истоков современной информатики, показал, что алгебра логики применима для описания самых разных процессов, в том числе релейных и транзисторных схем.

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

Так, примерами высказываний могут служить такие фразы, как “сегодня идет дождь”, или “завтра я не пойду в институт”. Определение истинности высказывания не всегда тривиально. Так, например: Великая теорема Ферма Для любого натурального числа \(n>2\) уравнение \[ a^n + b^n = c^n\] Не имеет решений в целых ненулевых числах \(a,\,b,\,c\) Как известно, сформулированная Пьером Ферма в 1637 году, была окончательно доказана только в 1994.

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

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

Например, фраза “это высказывание является ложным” не может считаться высказыванием, поскольку бессмысленно говорить о его истинности или ложности. Причиной парадокса является структура фразы: она ссылается сама на себя. Подобные парадоксы могут быть устранены введением следующего определения: Элементарное высказывание это такое высказывание, никакая часть которого не является высказыванием.

Следует заметить, что высказыванием в строгом смысле является только утверждение о конкретных объектах. Если речь идет о неких переменных, например, “x – рациональное число”, то мы говорим о неких функциях, имеющих значение “истина” или “ложь”. Такие функции называются предикатами.

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

Если мы договоримся считать за аксиому, что “солнце светит ночью”, то есть, договоримся что это высказывание истинно, то в рамках нашей аксиоматики сможем делать какие-то обоснованные выводы. Эти выводы, конечно, не будут иметь много общего с действительностью. Примерами таких отвлеченных, на первый взгляд, систем, может служить, например, геометрия Лобачевского, которая имеет не слишком много общего с нашим псевдоевклидовым пространством.

Примерами таких отвлеченных, на первый взгляд, систем, может служить, например, геометрия Лобачевского, которая имеет не слишком много общего с нашим псевдоевклидовым пространством. Различные языковые связки, такие, как “не”, “если …, то …”, “или”, “и”, и т.п.

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

Введем некоторые из них. Конъюнкция, или логическое умножение логическая операция, ставящая в соответствие двум элементарным высказываниям новое высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания истинны. Конъюнкция обозначается различными способами, в частности, амперсандом \(a \,\&\,b\), точкой \(a \cdot b\), или “крышкой” \(a \wedge b\), и соответствует языковой связке “и”.

Мы будем в основном использовать амперсанд.

Поскольку оба исходных высказывания имеют по два возможных значения, и конъюнкция имеет два возможных значения, мы можем записать это определение в виде таблицы истинности: 0 0 0 0 1 0 1 0 0 1 1 1 Дизъюнкция, или логическое сложение логическая операция, ставящая в соответствие двум элементарным высказываниям новое высказывание, являющееся истинным тогда и только тогда, когда хотя бы одно из исходных высказываний истинно. Дизъюнкция соответствует союзу “или”, и обозначается плюсом \(a+b\), или “галочкой” \(a\vee b\).

Мы будем использовать в основном второй вариант. Таблица истинности дизъюнкции, по определению: 0 0 0 0 1 1 1 0 1 1 1 1 Строгая дизъюнкция, или сложение по модулю 2 логическая операция, ставящая в соответствие двум элементарным высказываниям новое высказывание, являющееся истинным тогда и только тогда, когда только одно из исходных высказываний истинно. Строгая дизъюнкция соответствует связке “либо …, либо …”, и обозначается плюсом в кружочке \(a\oplus b\), или треугольником \(a\vartriangle b\).

Будем в основном пользоваться первым обозначением. Таблица истинности, по определению: 0 0 0 0 1 1 1 0 1 1 1 0 Импликация логическая операция, ставящая в соответствие двум элементарным высказываниям новое высказывание, являющееся ложным тогда и только тогда, когда первое из исходных высказываний (условие) истинно, а второе (следствие) – ложно. Импликация соответствует связке “если …, то …”, и обозначается стрелкой \(a \rightarrow b\), или \(a \Rightarrow b\) Таблица истинности, по определению: 0 0 1 0 1 1 1 0 0 1 1 1 Импликация, на первый взгляд, имеет не очевидное определение: как вдруг из ложных условий получается истинное следствие.

Однако, в математике это никакая не новость. Например, возьмем очевидно ложное утверждение “один равен двум”: \[1 = 2\] \[2 = 1\] Складывая эти равенства, получим очевидно истинный результат: \[3=3.\] С другой стороны, из заведомо истинных посылок формально нельзя вывести ложный результат (конечно, человеческий фактор никто не отменял, но человеческий фактор выходит за пределы рассмотрения формальной логики). Эквивалентность логическая операция, ставящая в соответствие двум элементарным высказываниям новое высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания одновременно истинны или одновременно ложны.

Эквивалентность соответствует связке “тогда и только тогда, когда”, и обозначается \(a \Leftrightarrow b\), или \(a \equiv b\), или \(a \sim b\), или \(a \leftrightarrow b\).

Будем в основном пользоваться первыми двумя обозначениями.

Таблица истинности, по определению: 0 0 1 0 1 0 1 0 0 1 1 1 Инверсия, или отрицание логическая операция, ставящая в соответствие элементарному высказыванию новое высказывание, являющееся истинным тогда и только тогда, исходное ложно. Инверсия соответствует связке “не”, и обозначается \(\neg a\), или \(\;\overline{a}\;\), или \(!a\).

Будем в основном пользоваться первыми двумя обозначениями.

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

Логическая формула любая переменная, а так же любая из констант “0” (“ложь”) и “1” (“истина”) Любая комбинация логических формул, составленная с помощью логических операций.

Эквивалентные формулы такие формулы, которые зависят от одного и того же набора переменных, и при одинаковых значениях этих переменных, формулы так же имеют одинаковые значения. Обозначать будем знаком равенства. Существуют следующие “законы” алгебры логики, определяющие некий набор эквивалентных формул: Законы коммутативности \[x \,\&\,y = y \,\&\,x\] \[x \vee y = y\vee x\] Законы ассоциативности \[ (x \,\&\,y) \,\&\,z = x \,\&\,(y \,\&\,z)\] \[ (x \vee y) \vee z = x \vee(y \vee z)\] Законы поглощения \[x\vee 0 = x\] \[x\,\&\,1 = x\] Законы дистрибутивности \[ x\,\&\,(y\vee z) = (x\,\&\,y) \vee(x\,\&\,z)\] \[ x\vee(y\,\&\,z) = (x \vee y) \,\&\,(x\vee z)\] Закон противоречия \[ x \,\&\,\;\overline{x}\; = 0\] Закон исключения третьего \[ x \vee\;\overline{x}\; = 1\] Закон равносильности \[ x \,\&\,x = x\] \[ x \vee x = x \] Закон двойного отрицания \[\;\overline{\;\overline{x}\;}\; = x \] Законы де Моргана \[ \;\overline{x\,\&\,y}\; = \;\overline{x}\; \vee\;\overline{y}\; \] \[ \;\overline{x\vee y}\; = \;\overline{x}\; \,\&\,\;\overline{y}\; \] Законы поглощения \[ x\vee(x\,\&\,y) = x\] \[ x\,\&\,(x\vee y) = x\] Все перечисленные законы элементарно доказываются составлением таблиц истинности.

Например, первый закон де Моргана: 0 0 0 1 1 1 1 0 1 0 1 1 0 1 1 0 0 1 0 1 1 1 1 1 0 0 0 0 3 и 6 столбец одинаковы, следовательно, соответствующие формулы эквивалентны. Введем еще одно определение Тавтология логическая формула, которая всегда истинна.

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

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

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

  • Составляется единое логическое выражение, соответствующее условию задачи. По условию задачи оно является истинным.
  • Решение формулируется в исходных терминах задачи.
  • Полученное выражение упрощается, либо составляется таблица истинности для него (либо и то, и другое)
  • Условия задачи записываются в виде логических формул
  • Выбирается решение задачи (случаи, когда условие истинно)
  • Из условий задачи выделяются простые высказывания и обозначаются как логические переменные.

Пример: () На весеннем фестивале, четыре садовника показывали выращенные ими розы.

Всего розы были четырех цветов и у каждого садовника было по две розы.

Известно, что

  1. У третьего была синяя роза, но не было зеленой
  2. У одного из садовников с зеленой розой не было красной
  3. Ни у одного из садовников с желтой розой не было зеленой
  4. Ни у кого нет роз двух одинаковых цветов
  5. У первого была желтая роза
  6. У второго не было красной розы

Введем переменные, в которых название переменной соответствует цвету, а индекс – садовнику (номеру). Это автоматически учитывает условие “Ни у кого нет роз двух одинаковых цветов”.

Тогда условия задачи запишутся в виде:

  1. \((y_1\rightarrow\;\overline{g_1}\;) \,\&\,(y_2\rightarrow\;\overline{g_2}\;)\,\&\,(y_3\rightarrow\;\overline{g_3}\;)\,\&\,(y_4\rightarrow\;\overline{g_4}\;)\)
  2. \((g_1\rightarrow\;\overline{r_1}\;) \oplus(g_2\rightarrow\;\overline{r_2}\;)\oplus(g_3\rightarrow\;\overline{r_3}\;)\oplus(g_4\rightarrow\;\overline{r_4}\;)\)
  3. \(y_1\)
  4. \(\;\overline{r_2}\;\)
  5. \(b_3 \,\&\,\;\overline{g_3}\;\)

Дополнительно, у каждого садовника по условиям задачи по две розы: Поэтому, если у садовника есть розы двух цветов, то роз двух других цветов у него нет. Учтем подразумеваемые импликации постфактум. Далее для простоты записи, амперсанды опускаются (если между переменными нет ничего – значит там амперсанд).

В случае отсутствия скобок, сначала применяется конъюнкция, потом все остальное. Рассматривая последнее условие: \((y_1\rightarrow\;\overline{g_1}\;) (y_2\rightarrow\;\overline{g_2}\;)(y_3\rightarrow\;\overline{g_3}\;)(y_4\rightarrow\;\overline{g_4}\;)\) Первая импликация истинна, только если \(\;\overline{g_1}\;\) истинно. Предпоследняя импликация истинна всегда, \(\;\overline{g_3}\;\).

Можем переписать в виде: \(y_1 \;\overline{g_1}\; (y_2\rightarrow\;\overline{g_2}\;) (y_4\rightarrow\;\overline{g_4}\;)\) Рассмотрим предпоследнее условие \[ (g_1 \rightarrow\;\overline{r_1}\;) \oplus(g_2 \rightarrow\;\overline{r_2}\;) \oplus(g_3 \rightarrow\;\overline{r_3}\;) \oplus(g_4 \rightarrow\;\overline{r_4}\;) \] Первая импликация всегда истинна, поскольку \(\;\overline{g_1}\;\), вторая всегда истинна, поскольку \(\;\overline{r_2}\;\), третья всегда истинна, поскольку \(\;\overline{g_3}\;\).

Получаем: \[ 1 \oplus 1 \oplus 1 \oplus(g_4 \rightarrow\;\overline{r_4}\;) \] \[ 1 \oplus(g_4 \rightarrow\;\overline{r_4}\;) \] Легко показать, что \(1 \oplus x = \;\overline{x}\;\).

Тогда условие принимает вид \[ \;\overline{g_4 \rightarrow\;\overline{r_4}\;}\; \] Импликацию можно представить в виде \(x \rightarrow y = \;\overline{x}\; \vee y\) Применяя закон де Моргана, \[ r_4 g_4 \] Записывая все условия вместе: \[ y_1 \;\overline{g_1}\; \;\overline{r_2}\; (\;\overline{y_2}\; \vee\;\overline{g_2}\;) (\;\overline{y_4}\; \vee\;\overline{g_4}\;) b_3 \;\overline{g_3}\; g_4 r_4 \] Учитывая \(g_4 (\;\overline{y_4}\; \vee\;\overline{g_4}\;) = g_4 \;\overline{y_4}\;\), \[ y_1 \;\overline{g_1}\; \;\overline{r_2}\; (\;\overline{y_2}\; \vee\;\overline{g_2}\;) b_3 \;\overline{g_3}\; \;\overline{y_4}\; g_4 r_4 \] Известно, что зеленые розы должны быть у двух садовников: \[ \;\overline{g_1}\; \;\overline{g_2}\; g_3 g_4 \vee\;\overline{g_1}\; g_2 \;\overline{g_3}\; g_4 \vee\;\overline{g_1}\; g_2 g_3 \;\overline{g_4}\; \vee g_1 \;\overline{g_2}\; \;\overline{g_3}\; g_4 \vee g_1 \;\overline{g_2}\; g_3 \;\overline{g_4}\; \vee g_1 g_2 \;\overline{g_3}\; \;\overline{g_4}\; \] А так как \(\;\overline{g_3}\;\) и \(\;\overline{g_1}\;\) \[ \;\overline{g_1}\; g_2 \;\overline{g_3}\; g_4 \] Получаем \(g_2\), тогда \(g_2 (\;\overline{y_2}\; \vee\;\overline{g_2}\;) = g_2 \;\overline{y_2}\;\) Аналогично для желтых: \[ y_1 \;\overline{y_2}\; y_3 \;\overline{y_4}\; \] Получаем \(y_3\). Поскольку \(y_3 b_3\), можно утверждать \(\;\overline{r_3}\; \;\overline{g_3}\;\) Для красных тогда: \[ r_1 \;\overline{r_2}\; \;\overline{r_3}\; r_4 \] Получаем \(r_1\). Поскольку \(r_1 y_1\), можем утверждать \(\;\overline{b_1}\; \;\overline{g_1}\;\) Для синих: \[ \;\overline{b_1}\; b_2 b_3 \;\overline{b_4}\; \] Получаем \(b_2\).

Итого \[ y_1 r_1 g_2 b_2 b_3 y_3 g_4 r_4 \]

  • Вообще сейчас считается, что у пространства, в котором мы находимся, времеподобная метрика Миньковского.

Законы логики на уроках информатики и ИКТ

  1. , учитель информатики и ИКТ

Разделы: Урок по информатике рассчитан на учащихся 10-х классов общеобразовательной школы, в учебном плане которой входит раздел «Алгебра логики». Учащимся очень нелегко дается эта тема, поэтому мне, как учителю, захотелось заинтересовать их в изучении законов логики, упрощении логических выражений и с интересом подойти к решению логических задач.

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

В связи с предоставлением информационного пространства, у меня появилась возможность выкладывать свои уроки в оболочке «learning».

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

План урока

  • Основные понятия и определения, выложенные в «learning» — 10 минут.
  • Домашнее задание – 5 минут.
  • Объяснение нового материала, с привлечением компьютера – 25 минут.
  • Материал для любознательных – 5 минут.

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

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

Первые три из вышеперечисленных законов были выявлены и сформулированы Аристотелем, а закон достаточного основания — Г. Лейбницем. Закон тождества: в процессе определенного рассуждения всякое понятие и суждение должны быть тождественны самим себе.

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

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

Ложные же мысли доказать нельзя. Есть хорошая латинская пословица:

«Ошибаться свойственно всякому человеку, но настаивать на ошибке свойственно только глупцу»

.

Формулы этого закона нет, так как он имеет только содержательный характер.

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

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

Законы алгебры высказываний (алгебры логики) — это тавтологии.

Иногда эти законы называются теоремами.

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

Первые четыре из приведенных ниже законов являются основными законами алгебры высказываний. Закон тождества: А=А Всякое понятие и суждение тождественно самому себе.

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

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

Хождение в школу — движение. Следовательно, хождение в школу вечно слово «движение» используется в двух разных смыслах (первое — в философском смысле — как атрибут материи, второе — в обыденном смысле — как действие по перемещению в пространстве), что приводит к ложному выводу. Закон непротиворечия: Не могут быть одновременно истинными суждение и его отрицание.

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

Иногда этот закон формулируется так: два противоречащих друг другу высказывания не могут быть одновременно истинными. Примеры невыполнения закона непротиворечия: 1.

На Марсе есть жизнь и на Марсе жизни нет. 2. Оля окончила среднюю школу и учится в X классе. Закон исключенного третьего: В один и тот же момент времени высказывание может быть либо истинным, либо ложным, третьего не дано.

Истинно либо А, либо не А. Примеры выполнения закона исключенного третьего: 1.

Число 12345 либо четное, либо нечетное, третьего не дано. 2. Предприятие работает убыточно или безубыточно. 3. Эта жидкость является или не является кислотой.

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

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

Рассмотрим следующее высказывание: Это предложение ложно. Оно не может быть истинным, потому что в нем утверждается, что оно ложно. Но оно не может быть и ложным, потому что тогда оно было бы истинным.

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

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

Например, определим, чему эквивалентно (равносильно) А (двойное отрицание А, т. е. отрицание отрицания А). Для этого построим таблицу истинности: По определению равносильности мы должны найти тот столбец, значения которого совпадают со значениями столбца А.

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

Например, высказывание А = Матроскин — кот эквивалентно высказыванию А = Неверно, что Матроскин не кот.

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

Аналогично от повторения на улице тепло, на улице тепло,.

ни на один градус теплее не станет. Законы коммутативности: A v B = B v A А & В = В & А Операнды А и В в операциях дизъюнкции и конъюнкции можно менять местами.

Законы ассоциативности: A v(B v C) = (A v B) v C; А & (В & C) = (A & В) & С. Если в выражении используется только операция дизъюнкции или только операция конъюнкции, то можно пренебрегать скобками или произвольно их расставлять. Законы дистрибутивности: A v (B & C) = (A v B) &(A v C) (дистрибутивность дизъюнкции относительно конъюнкции) А & (B v C) = (A & B) v (А & C) (дистрибутивность конъюнкции относительно дизъюнкции) Закон дистрибутивности конъюнкции относительно дизъюнкции ана­логичен дистрибутивному закону в алгебре, а закон дистрибутивности дизъюнкции относительно конъюнкции аналога не имеет, он справедлив только в логике.

Поэтому необходимо его доказать.

Доказательство удобнее всего провести с помощью таблицы истинности: Законы поглощения: A v (A & B) = A A & (A v B) = A Проведите доказательство законов поглощения самостоятельно. Законы де Моргана: Словесные формулировки законов де Моргана: 1.

2. Мнемоническое правило: в левой части тождества операция отрицания стоит над всем высказыванием. В правой части она как бы разрывается и отрицание стоит над каждым из простых высказываний, но одновременно меняется операция: дизъюнкция на конъюнкцию и наоборот. Примеры выполнения закона де Моргана: 1) Высказывание Неверно, что я знаю арабский или китайский язык тождественно высказыванию Я не знаю арабского языка и не знаю китайского языка.

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

Существуют правила замены данных операций на последовательности операций отрицания, дизъюнкции и конъюнкции.

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

Рассмотрим следующий пример. Пусть дано высказывание: Е = Неверно, что если я выиграю конкурс, то получу приз. Пусть А = Я выиграю конкурс, В = Я получу приз. Тогда Отсюда, Е = Я выиграю конкурс, но приз не получу. Интерес представляют и следующие правила: Доказать их справедливость можно также с помощью таблиц истинности.

Интерес представляют и следующие правила: Доказать их справедливость можно также с помощью таблиц истинности. Интересно их выражение на естественном языке.

Например, фраза Если Винни-Пух съел мед, то он сыт тождественна фразе Если Винни-Пух не сыт, то меда он не ел. Задание: придумайте фразы-примеры на данные правила.

2. Основные понятия и определения в Приложении 1 3.

Материал для любознательных в Приложении 2 4. Домашнее задание 1) Выучить законы логики, используя курс «Алгебры логики», размещенный в информационном пространстве (www.learning.9151394.ru). 2) Проверить на ПК доказательство законов де Моргана, построив таблицу истинности.

Приложения

  • Материал для любознательных ().
  • Основные понятия и определения ().

3.07.2010 Поделиться страницей:

Урок 24§20.1. Основные законы алгебры логики

| | | | | Основные законы алгебры логики Содержание урока:

20.1. Основные законы алгебры логики.

Пример 4 20.1. Основные законы алгебры логики. Примеры 2 и 3 САМОЕ ГЛАВНОЕ Пример 4. Для какого наименьшего неотрицательного целого десятичного числа а выражение

тождественно истинно (т.

е. принимает значение 1 при любом неотрицательном целом значении десятичной переменной х)? Здесь & — поразрядная конъюнкция двух неотрицательных целых десятичных чисел.

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

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

Перепишем исходное выражение в наших обозначениях:

Рассмотрим предикат М(х) = (х & 28 ≠ 0).

В числе 28 = 111002 4-й, 3-й и 2-й биты содержат единицы, а 1-й и 0-й — нули. Следовательно, множеством истинности этого предиката являются такие числа х, у которых хотя бы один из битов с номерами 4, 3 или 2 содержит единицу.

Если и 4-й, и 3-й, и 2-й биты числа х нулевые, то высказывание х & 28 ≠ 0 будет ложным. Рассмотрим предикат N(x) = (х & 45 ≠ 0).

В числе 45 = 1011012 5-й, 3-й, 2-й и 0-й биты содержат единицы, 4-й и 1-й — нули. Следовательно, множеством истинности этого предиката являются такие числа х, у которых хотя бы один из битов с номерами 5, 3, 2 или 0 содержит единицу. Если и 5-й, и 3-й, и 2-й, и 0-й биты числа х нулевые, то высказывание х & 45 ≠ 0 будет ложным.

Рассмотрим предикат К(х) = (х & 17 = 0).

В числе 17 = 100012 3-й, 2-й и 1-й биты содержат нули, 4-й и 0-й — единицы. Побитовая конъюнкция 17 и х будет равна нулю, если в числе х 4-й и 0-й биты будут содержать нули.

Множество истинности этого предиката — все х с нулями в 4-м и 0-м битах. По условию задачи надо, чтобы

Запишем это выражение для рассмотренных множеств истинности:

Объединением множеств М и N являются все двоичные числа, у которых хотя бы один из битов с номерами 5, 4, 3, 2, 0 содержит единицу. Пересечением этого множества с множеством К будут все двоичные числа, у которых биты с номерами 4 и 0 будут заняты нулями, т.

е. такие двоичные числа, у которых хотя бы один из битов с номерами 5, 3, 2 содержит 1.

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

Этим условиям удовлетворяет число 1011002. Действительно, единицы в нём стоят в тех и только в тех битах, которые нужны для выполнения условия х & а ≠ 0. Итак, требуемое число 1011002 или 4410.

Приведите пример такого десятичного числа а, что для него х & а ≠ 0 при любом неотрицательном целом значении десятичной переменной х, но само число а не является минимально возможным. Пример 5. Выясним, сколько решений имеет следующая система из двух уравнений:

Рассмотрим первое уравнение: (х1 → х2) & (х2 → х3) & (х3 → x4) = 1.

Конъюнкция истинна тогда и только тогда, когда истинны все образующие её высказывания. Следовательно, каждая из трёх входящих в конъюнкцию импликаций должна быть равна 1. Начнем строить дерево решений, представив на нём значения переменных х1 и х2 при которых х1 → х2 = 1.

Продолжим строить дерево решений.

Значения переменной х3 будем выбирать такими, чтобы при имеющихся х2 импликация х2 → х3 оставалась истинной.

То же самое проделаем для переменной х4.

На дереве видно, что рассматриваемое нами уравнение имеет 5 решений — 5 разных наборов значений логических переменных x1, х2, х3, х4, при которых выполняется равенство:

Следовательно, как и первое уравнение, это уравнение имеет 5 решений. Представим их в табличной форме:

Решение исходной системы логических уравнений — это множество различных наборов значений логических переменных х1, х2, х3, х4, у1, у2, у3, у4 таких, что при подстановке каждого из них в систему оба уравнения превращаются в истинные равенства. Начнём строить такие наборы или двоичные цепочки.

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

Всего мы можем построить 5 • 5 = 25 решений системы.

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

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

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

Некоторые преобразования логических формул похожи на преобразования формул в обычной алгебре (вынесение общего множителя за скобки, использование переместительного и сочетательного законов и т.п.), тогда как другие преобразования основаны на свойствах, которыми не обладают операции обычной алгебры (использование распределительного закона для конъюнкции, законов поглощения, склеивания, де Моргана и др.).ЗаконФормулировка1. Закон тождестваХ = ХВсякое высказывание тождественно самому себе.

2. Закон исключенного третьего X \/ ¬X = 1Высказывание может быть либо истинным, либо ложным, третьего не дано. Следовательно, результат логического сложения высказывания и его отрицания всегда принимает значение «истина».3. Закон непротиворечия X/\ ¬X = 0Высказывание не может быть одновременно истинным и ложным.

Если высказывание Х истинно, то его отрицание НЕ Х должно быть ложным.

Следовательно, логическое произведение высказывания и его отрицания должно быть ложно.4. Закон двойного отрицания¬¬X = X Если дважды отрицать некоторое высказывание, то в результате получим исходное высказывание.5. Переместительный (коммутативный) законX /\ Y = Y /\ XX /\ Y = YX /\ Результат операции над высказываниями не зависит от того, в каком порядке берутся эти высказывания.6.

Сочетательный (ассоциативный) закон(X \/Y) \/Z = X \/ (Y \/Z)(X/\Y)/\Z=X/\(Y/\Z)При одинаковых знаках скобки можно ставить произвольно или вообще опускать.5. Распределительный (дистрибутивный) закон(X /\ Y) \/ Z= (X /\ Z) \/ (Y /\ Z)(X /\ Y) \/ Z = (X \/ Z) /\ (Y \/ Z)Определяет правило выноса общего высказывания за скобку.7. Закон общей инверсии Закон де Моргана¬(X \/ Y) = ¬X /\ ¬Y¬(X /\ Y) = ¬X \/ ¬YЗакон общей инверсии.

8. Закон равносильности (идемпотентности)A\/A= A;A/\ A = A.от латинских слов idem — тот же самый и potens —сильный 9. Законы исключения констант:A\/ 1 = 1, A\/ 0 = A;A/\1 = A, A/\0 = 0. 10. Закон поглощения:A\/ (A/\B) = A;A/\ (A\/B) = A.

11. Закон исключения (склеивания):(A/\B) \/ (¬A/\B) = B;(A\/B)/\(¬A \/B) = B. 12. Закон контрапозиции(правило перевертывания):(A<=>B) = (B<=>A). 13. А => В = ¬A \/ В;14. ¬ (A=>B)=A/\B 14.

А <=>В = (А /\ В) \/ (¬A /\ ¬B); 15.

А <=>В = (¬A \/ В) /\ (А \/¬B). Применим законы алгебры логики. Покажем на примере как можно упростить логическое выражение: 1) (A/\B) \/ (A/\¬B) = A /\ (B \/ B)= A /\ 1 = A 2) ¬ (X \/ Y) /\ (X /\ ¬Y)Законы алгебры логики применяются в следующей последовательности: правило де Моргана, сочетательный закон, правило операций переменной с её инверсией и правило операций с константами.

¬ (X \/ Y) /\ (X /\ ¬Y) = ¬ X /\ ¬Y /\ (X /\ ¬Y) = ¬ X /\ X/\¬Y /\¬Y= 0 ¬Y /\¬Y3) применяется правило де Моргана, выносится за скобки общий множитель, используется правило операций переменной с её инверсией 4) ¬ X /\ Y \/ ¬ (X \/ Y) \/ X = ¬ X /\ Y \/ ¬ X /\ ¬Y \/ X= ¬ X /\ (Y \/ ¬Y) \/ X= ¬ X \/ X= 1

  1. E-mail для связи:
  2. MIR-LOGIKI.RU

© Copyright © 2018, МИР ЛОГИКИ. Копирование материалов сайта допускается только при указании гиперссылки на mir-logiki.ru.

Малый математический факультет

Алгебра – это раздел математики, предназначенный для описания действий над переменными величинами, которые принято обозначать строчными буквами латинского алфавита – а, b, x, y и т.д.

Действия над переменными величинами записываются в виде математических выражений.

Термин «логика» происходит от древнегреческого “logos”, означающего «слово, мысль, понятие, рассуждение, закон».

Алгеброй логики называется аппарат, который позволяет выполнять действия над высказываниями. Алгебру логику называют также алгеброй Буля, или булевой алгеброй, по имени английского математика Джорджа Буля, разработавшего в XIX веке ее основные положения. В булевой алгебре высказывания принято обозначать прописными латинскими буквами: A, B, X, Y.

В алгебре Буля введены три основные логические операции с высказываниями?

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

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

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

По аналогии с понятием функции в алгебре сложное логическое выражение содержит аргументы, которыми являются высказывания. В качестве основных логических операций в сложных логических выражениях используются следующие: • НЕ (логическое отрицание, инверсия); • ИЛИ (логическое сложение, дизъюнкция); • И (логическое умножение, конъюнкция).

Логическое отрицание является одноместной операцией, так как в ней участвует одно высказывание. Логическое сложение и умножение — двуместные операции, в них участвует два выска¬зывания.

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

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

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

  1. таблица истинности одноместной логической операции состоит из двух строк: два различных значения аргумента — «истина» (1) и «ложь» (0) и два соответствующих им значения функции;
  2. в таблице истинности двуместной логической операции — четыре строки: 4 различных сочетания значений аргументов — 00, 01, 10 и 11 и 4 соответствующих им значения функции;
  3. если число высказываний в логическом выражении N, то таблица истинности будет содержать 2N строк, так как существует 2N различных комбинаций возможных значений аргументов.

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

Результатом операции НЕ является следующее: • если исходное выражение истинно, то результат его отрицания будет ложным; • если исходное выражение ложно, то результат его отрицания будет истинным. Для операции отрицания НЕ приняты следующие условные обозначения: не А, ?, not A, ¬А. Результат операции отрицания НЕ определяется следующей таблицей истинности: A не А 0 1 1 0 Результат операции отрицания истинен, когда исходное высказывание ложно, и наоборот.

Приведем примеры отрицания. 1.

Высказывание «Земля вращается вокруг Солнца» истинно.

Высказывание «Земля не вращается вокруг Солнца» ложно.

2. Высказывание «Уравнение у = 4х + 3 в промежутке -2 3.

Высказывание «4 — простое число» ложно. Высказывание «4 — не простое число» истинно.

Принцип работы переключателя настольной лампы таков: если лампа горела, переключатель выключает ее, если лампа не горела — включает ее.

Такой переключатель можно счи¬тать электрическим аналогом операции отрицания.

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

Высказывания, являющиеся исходными для логической операции, называют аргументами. Результатом операции ИЛИ является выражение, которое бу¬дет истинным тогда и только тогда, когда истинно будет хотя бы одно из исходных выражений. Применяемые обозначения: А или В, А V В, A or B.

Результат операции ИЛИ опреде¬ляется следующей таблицей истинности: A B А или B 0 0 0 0 1 1 1 0 1 1 1 1 Результат операции ИЛИ истинен, когда истинно А, либо истинно В, либо истинно и А и В одновременно, и ложен тогда, когда аргументы А и В — ложны. Приведем примеры логического сложения.

1. Рассмотрим высказывание

«В библиотеке можно взять книгу или встретить знакомого»

.

Это высказывание формально мож¬но представить так: С = А ?

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

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

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

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

Применяемые обозначения: А и В, А ? В, A & B, A and B. Результат операции И определяется следующей таблицей истинности: A B А и B 0 0 0 0 1 0 1 0 0 1 1 1 Результат операции И истинен тогда и только тогда, когда истинны одновременно высказывания А и В, и ложен во всех остальных случаях. Приведем примеры логического умножения.

1. Рассмотрим высказывание «Умение и настойчивость приводит к достижению цели».

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

Ток протекает только при одном условии — все составляющие цепи должны быть исправны. Операция «ЕСЛИ-ТО» — логическое следование (импликация) Эта операция связывает два простых логических выражения, из которых первое является условием, а второе — следствием из этого условия. Применяемые обозначения: если А, то В; А влечет В; if A then В; А?

В. Таблица истинности: A B А ?

B 0 0 1 0 1 1 1 0 0 1 1 1 Результат операции следования (импликации) ложен только тогда, когда предпосылка А истинна, а заключение В (следствие) ложно.

Приведем примеры операции следования.

1. Рассмотрим высказывание «Если идет дождь, то на улице сыро».

Здесь исходные высказывания «Идет дождь» и «На улице сыро». Если не идет дождь и не сыро на улице, результат операции следования — истина.

На улице может быть сыро и без дождя, например, когда прошла поливочная машина или дождь прошел накануне. Результат операции ложен только тогда, когда дождь идет, а на улице не сыро. 2. Рассмотрим два высказывания: А {х делится на 9}, В {х делится на 3}.

Операция А ? В означает следующее: «Если число делится на 9, то оно делится и на 3». Рассмотрим возможные варианты: ? А — ложно, В — ложно (1-я строка таблицы истинности).

Можно найти такие числа, для которых истиной является высказывание «если А — ложно, то и В — ложно».

Например, х = 4, 17, 22. ? А — ложно, В — истинно (2-я строка таблицы истинности). Можно найти такие числа, для которых истиной является высказывание «если А — ложно, то В — истинно».

Например, х = б, 12, 21. ? А — истинно, В — ложно (3-я строка таблицы истинности).

Невозможно найти такие числа, которые делились бы на 9, но не делились на 3.

Истинная предпосылка не может приводить к ложному результату импликации. ? А — истинно, В — истинно (4-я строка таблицы истинности).

Можно найти такие числа, для которых истиной является высказывание «если А — истинно, то и В — истинно». Например, х = 9, 18, 27. Применяемое обозначение: А ?

В, А ~ В. Таблица истинности: A B А?B 0 0 1 0 1 0 1 0 0 1 1 1 Результат операции эквивалентность истинен только тогда, когда А и В одновременно истинны или одновременно ложны. Приведем примеры операции эквивалентности: 1. День сменяет ночь тогда и только тогда, когда солнце скрывается за горизонтом; 2.

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

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

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

Поэтому, для вас работают бесплатные эксперты-консультанты!

Расскажите о вашей проблеме, и мы поможем ее решить! Задайте вопрос прямо сейчас!

  • Анонимно
  • Профессионально

Задайте вопрос нашему юристу!

Расскажите о вашей проблеме и мы поможем ее решить!

+