Законы поглощения доказательство

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

Запишем алгоритм выполнения операций ИЛИ и И, расположив строки таблицы для операции И в обратном порядке – снизу вверх:

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

В этом состоит принцип двойственности, который в общем виде записывается так:

, .

Для любого числа переменных это правило, называемое еще теоремой де Моргана, имеет вид:

.

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

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

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

Теоремы для одной переменной:

A \/ 0 = A 4. A \/ Ā = 1 7. A · A = A

2. A \/ 1 = 1 5. A · 0 = 0 8. A · Ā = 0

3. A \/ A = A 6. A · 1 = 1 9.

Теоремы для двух и более переменных:

10. а) A \/ B = B \/ A, б) AB = BA

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

11. а) A \/ B \/ C = A \/ (B \/ C) = (A \/ B) \/ C,

б) ABC = A(BC) = (AB)C – сочетательный закон.

12. а) A (B \/ C) = AB \/ AC, б) A \/ BC = (A \/ B)(A \/ C) – распределительный закон.

Данная теорема и все последующие вытекают из принципа двойственности. Применим его к выражению 12, а:

– левая часть,

– правая часть.

Введя новые обозначения: , получим обозначения: , а это и есть теорема 12, б.

13. а) A \/ AB = A, б) A(A \/ B) = A

– закон поглощения (A поглощает B).

Доказательство 13, а:

A \/ AB = A(1 \/ B) = A · 1 = A, (используя теоремы 2, 6).

Теорема 13, б следует из принципа двойственности.

14. а) , б) .

, (используя теоремы 8 и 1).

Теорема 14, б следует из принципа двойственности.

15. а) AB \/ ĀB = B, į) (A \/ B)(Ā \/ B) = B, закон склеивания (склеивание по A).

Доказательство 15, а:

AB \/ ĀB = B(A \/ Ā) = B · 1 = B, (используя теоремы 4 и 6).

Теорема 15, б следует из принципа двойственности.

Мало ли что я обещал гоям?
Российскую пенсию будут получать только израильтяне!
Мой кошелёк — Минц всё равно уже вывез деньги ПФ за рубеж.

Где деньги на пенсии? Как врёт правительство?

bourabai.ru

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

  • научиться применять законы алгебры логики для упрощения выражений;
  • развивать логическое мышлении;
  • прививать внимательность

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

Перечислим наиболее важные из них:

  1. X X Закон тождества.
  2. Закон противоречия
  3. Закон исключенного третьего
  4. Закон двойного отрицания
  5. Законы идемпотентности: X X X, X X C
  6. Законы коммутативности (переместительности): X Y Y X, X Y Y X
  7. Законы ассоциативности (сочетательности): (X Y) Z X (Y Z), (X Y) Z X (Y Z)
  8. Законы дистрибутивности (распределительности): X (Y Z) (X Y) (X Z), X (Y Z) (X Y) (X Z)
  9. Законы де Моргана ,
  10. X 1 X, X 0 X
  11. X 0 0, X 1 1

1-й закон сформулирован древнегреческим философом Аристотелем. Закон тождества утверждает, что мысль, заключенная в некотором высказывании, остается неизменной на протяжении всего рассуждения, в котором это высказывание фигурирует.

Закон противоречия говорит о том, что никакое предложение не может быть истинно одновременно со своим отрицанием. “Это яблоко спелое” и “Это яблоко не спелое”.

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

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

“ Неверно, что 2*2<>4”

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

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

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

Смысл законов де Моргана (Август де Морган (1806-1871) — шотландский математик и логик) можно выразить в кратких словесных формулировках:

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

— отрицание логической суммы эквивалентно логическому произведению отрицаний слагаемых.

1. Установить эквивалентны ли высказывания.

3. С помощью таблиц истинности доказать законы поглощения и склеивания.

I. Подача нового материала.

  1. Законы поглощения: X (X Y) X, X (X Y) X
  2. Законы склеивания: (X Y) ( Y) Y, (X Y) ( Y) Y

Доказать законы логики можно:

  1. с помощью таблиц истинности;
  2. с помощью равносильностей.

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

  1. (X Y) ( Y) (X+Y) *( +Y) X* + Y* + Y*Y+ X*Y Y* + Y + X*Y Y* + Y(1+X) Y* +Y Y( +1) Y склеивания
  2. X (X Y) X*X+X*Y X+X*Y X(1+Y) X поглощения

П. Практическая часть

1. Упрощение формул.

Пример 1. Упростить формулу (А+В)·* (А+С)

  1. Раскроем скобки ( A + B ) * ( A + C ) A * A + A * C + B * A + B * C
  2. По закону идемпотентности A*A A , следовательно , A*A + A*C + B*A + B*C A + A*C + B*A + B*C
  3. В высказываниях А и А*C вынесем за скобки А и используя свойство А+1 1, получим А+А*С+ B*A + B*C A*( 1 + С) + B*A + B*СA + B*A + B*С
  4. Аналогично пункту 3. вынесем за скобки высказывание А.
    A + B*A + B*С A ( 1 + B ) + B С A + B*С
    Таким образом, мы доказали закон дистрибутивности.

2. Преобразования “поглощение” и “склеивание”

Пример 2. Упростить выражение А+ A*B

Решение. A+A*B A ( 1 + B ) A — поглощение

Пример 3. Упростить выражение A*B+A*

Решение . A*B + A* A ( B + ) A — склеивание

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

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

  1. Воспользуемся формулой де Моргана, получим:
  2. Для выражения применим еще раз формулу де Моргана, получим:

4. Любую формулу можно тождественно преобразовать так, что в ней не будут использованы:

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

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

Решение. Воспользуемся законом двойного отрицания, а затем формулой де Моргана.

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

Все операции можно выразить через конъюнкцию и отрицание, дизъюнкцию и отрицание, импликацию и отрицание. Через эквиваленцию и отрицание остальные операции выразить нельзя.

Задание 1. Установить истинность высказывания .
Задание 2 Установить является ли высказывание тавтологией?
Задание 3. Установить эквивалентны ли высказывания.

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

;

;

.

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

;

;

.

;

.

lunina.21205s09.edusite.ru

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

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

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

1. Объяснение нового материала

Законы формальной логики

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

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

Закон тождества: в процессе определенного рассуждения всякое понятие и суждение должны быть тождественны самим себе.

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

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

Закон достаточного основания: всякая истинная мысль должна быть достаточно обоснована.

Последний закон говорит о том, что доказательство чего-либо предполагает обоснование именно и только истинных мыслей. Ложные же мысли доказать нельзя. Есть хорошая латинская пословица: «Ошибаться свойственно всякому человеку, но настаивать на ошибке свойственно только глупцу». Формулы этого закона нет, так как он имеет только содержательный характер. В качестве аргументов для подтверждения истинной мысли могут быть использованы истинные суждения, фактический материал, статистические данные, законы науки, аксиомы, доказанные теоремы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. На Марсе есть жизнь и на Марсе жизни нет.

2. Оля окончила среднюю школу и учится в X классе.

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

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

1. Число 12345 либо четное, либо нечетное, третьего не дано.

2. Предприятие работает убыточно или безубыточно.

3. Эта жидкость является или не является кислотой.

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

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

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

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

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

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

Если отрицать дважды некоторое высказывание, то в результате получается исходное высказывание. Например, высказывание А = Матроскинкот эквивалентно высказыванию А = Неверно, что Матроскин не кот.

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

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

Операнды А и В в операциях дизъюнкции и конъюнкции можно менять местами.

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)

(дистрибутивность конъюнкции
относительно дизъюнкции)

Закон дистрибутивности конъюнкции относительно дизъюнкции ана­логичен дистрибутивному закону в алгебре, а закон дистрибутивности дизъюнкции относительно конъюнкции аналога не имеет, он справедлив только в логике. Поэтому необходимо его доказать. Доказательство удобнее всего провести с помощью таблицы истинности:

Проведите доказательство законов поглощения самостоятельно.

Словесные формулировки законов де Моргана:

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

Примеры выполнения закона де Моргана:

1) Высказывание Неверно, что я знаю арабский или китайский язык тождественно высказыванию Я не знаю арабского языка и не знаю китайского языка.

2) Высказывание Неверно, что я выучил урок и получил по нему двойку тождественно высказыванию Или я не выучил урок, или я не получил по нему двойку.

Замена операций импликации и эквивалентности

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

Так, заменить операцию импликации можно в соответствии со следующим правилом:

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

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

Знание правил замены операций импликации и эквивалентности помогает, например, правильно построить отрицание импликации.

Рассмотрим следующий пример.

Пусть дано высказывание:

Е = Неверно, что если я выиграю конкурс, то получу приз.

Пусть А = Я выиграю конкурс,

В = Я получу приз.

Отсюда, Е = Я выиграю конкурс, но приз не получу.

Интерес представляют и следующие правила:

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

Интересно их выражение на естественном языке.

Если Винни-Пух съел мед, то он сыт

Если Винни-Пух не сыт, то меда он не ел.

Задание: придумайте фразы-примеры на данные правила.

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

3. Материал для любознательных в Приложении 2

4. Домашнее задание

1) Выучить законы логики, используя курс «Алгебры логики», размещенный в информационном пространстве (www.learning.9151394.ru).

2) Проверить на ПК доказательство законов де Моргана, построив таблицу истинности.

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

xn--i1abbnckbmcl9fb.xn--p1ai

Смотрите так же:

  • Закон кирхгофа спектральная плотность Закон Кирхгофа Кирхгоф, опираясь на второй закон термодинамики и анализируя условия равновес­ного излучения в изолированной системе тел, установил количественную связь между спектральной плотностью энергетической светимости и спектральной […]
  • Разбор слов Пребывание Разбор слов Пребывание ПРЕБЫВА́НИЕ, -я, ср. 1. Состояние по глаг. пребывать (во 2 знач.). Пребывание у власти. □ В последние дни пребывания в Гонконге погода значительно изменилась. И. Гончаров, Фрегат «Паллада». Месяцы пребывания в штабе […]
  • Следственный комитет комсомольск на амуре Комсомольский-на-Амуре следственный отдел на транспорте Адрес: 681013, Хабаровский край, г. Комсомольск-на-Амуре, ул. Красногвардейская, 34 Телефон: тел/факс 8 (4217) 54-36-88 Руководитель: Кутиков Дмитрий Сергеевич Заместитель […]
  • 2 закон динамики 2 закон динамики Для описания законов динамики вводят динамические параметры – массу m , силу и момент силы . Масса тела – мера количества вещества, содержащегося в теле. Масса проявляется в двух свойствах: а) в гравитации – в […]
  • Основы квалификации преступления учебник Теоретические основы квалификации преступлений: учебное пособие (fb2) Теоретические основы квалификации преступлений: учебное пособие 795K, 222с. (читать) (читать постранично) (скачать fb2) издано в 2008 г. (post) […]
  • Ошибка разрешении dns Windows Настройка параметров DNS-сервера Откройте диспетчер сервера. Чтобы открыть диспетчер сервера, щелкните Пуск, затем выберите Диспетчер сервера. В области результатов, в разделе Сводка по ролям щелкните элемент Добавить роли. В […]

Обсуждение закрыто.