Закон де моргана для трех переменных

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

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

Содержание

Определение [ править | править код ]

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

не (a и b) = (не a) или (не b) не (a или b) = (не a) и (не b)

В математике это выглядит так:

¬ ( a ∧ b ) = ¬ a ∨ ¬ b ¬ ( a ∨ b ) = ¬ a ∧ ¬ b <displaystyle <egin
eg <(awedge b)>=
eg vee
eg \
eg <(avee b)>=
eg wedge
eg
end
>> 000 или по-другому: 000 ( a ∧ b ) ¯ = a ¯ ∨ b ¯ ( a ∨ b ) ¯ = a ¯ ∧ b ¯ <displaystyle <egin<overline <(awedge b)>>=<overline >vee <overline >\<overline <(avee b)>>=<overline >wedge <overline >end>>

A ∩ B ¯ = A ¯ ∪ B ¯ A ∪ B ¯ = A ¯ ∩ B ¯ <displaystyle <egin<overline >=<overline >cup <overline >\<overline >=<overline >cap <overline >end>> 000 или по-другому: 000 ( A ∩ B ) C = A C ∪ B C , ( A ∪ B ) C = A C ∩ B C . <displaystyle <egin(Acap B)^=A^cup B^,\(Acup B)^=A^cap B^.end>>

Эти правила также действительны для множества элементов (семейств):

⋂ i ∈ I A i ¯ = ⋃ i ∈ I A i ¯ <displaystyle <overline <igcap _A_>>=igcup _<overline >>> 00000 и 00000 ⋃ i ∈ I A i ¯ = ⋂ i ∈ I A i ¯ <displaystyle <overline <igcup _A_>>=igcap _<overline >>> .

¬ ∀ x P ( x ) ≡ ∃ x ¬ P ( x ) , <displaystyle
eg forall x,P(x)equiv exists x,
eg P(x),> ¬ ∃ x P ( x ) ≡ ∀ x ¬ P ( x ) . <displaystyle
eg exists x,P(x)equiv forall x,
eg P(x).>

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

a ∧ b = ¬ ( ¬ a ∨ ¬ b ) <displaystyle awedge b=
eg (
eg vee
eg )> a ∨ b = ¬ ( ¬ a ∧ ¬ b ) <displaystyle avee b=
eg (
eg wedge
eg
)>

Если существует суждение, выраженное операцией логического умножения двух или более элементов, т. е. операцией «и»: ( A ∧ B ) <displaystyle <(Awedge B)>> , то для того, чтобы найти обратное ¬ ( A ∧ B ) <displaystyle <
eg (Awedge B)>> от всего суждения, необходимо найти обратное от каждого элемента и объединить их операцией логического сложения, т. е. операцией «или»: ( ¬ A ∨ ¬ B ) <displaystyle (
eg vee
eg )> . Закон работает аналогично в обратном направлении: ¬ ( A ∨ B ) = ( ¬ A ∧ ¬ B ) <displaystyle
eg (Avee B)=(
eg wedge
eg
)> .

Применение [ править | править код ]

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

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

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

Читайте также:  В одноклассниках не показывает ленту

Равносильности, выражающие основные законы алгебры логики

Каждая элементарная дизъюнкция содержит все переменные или их отрицания. Совершенная дизъюнктивная и совершенная конъюнктивная формы используются при проектировании элементов и узлов компьютера.

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

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

Логические основы компьютеров Материалы к урокам

x1x2x3F 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 б) запись функции в СДНФ (см. правило записи). Наборам 011, 101, 110, 111 соответствуют конъюнкции

, поэтому функция будет записана в следующем виде: в) упрощение функции.

Функции, записанные в СДНФ, первоначально упрощаются по правилу склеивания.

Затем применяются другие правила и тождественные соотношения. В данной функции первые три конъюнкции являются соседними с чет­вертой.

Функция не изменится, если к ней подписать еще две конъюнкции

После склеивания пар соседних конъюнкций окончательно получим: Можно было не подписывать конъюнкцию

, а просто склеить поочередно три первые конъюнкции с четвертой конъюнкцией.

_12Л_ЗаконыАЛ и Базис

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

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

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

1. Переместительный закон (аналогично обычной алгебре): —для дизъюнкции —для конъюнкции От перемены мест логических слагаемых (сомножителей) их логическая сумма (логическое произведение) не меняется. 2. Сочетательный закон (аналогично обычной алгебре): —для дизъюнкции —для конъюнкции Можно различным образом группировать логические переменные при выполнении операции конъюнкции (дизъюнкции) при этом значение булевой переключательной функции не изменяется. 3.

Sokolieds.ru

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

Используя законы алгебры логики, можно осуществлять тождественные преобразования формул, упрощать такие формулы. Это необходимо при создании логических схем и конструировании BEAM-роботов.

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

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

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

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

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

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

admin 15.03.2018 15.03.2018Консультации Основные теоремы и положения алгебры логики Запишем алгоритм выполнения операций ИЛИ и И, расположив строки таблицы для операции И в обратном порядке — снизу вверх: Если в этих таблицах переменные заменить их инверсиями, а знаки дизъюнкции на знаки конъюнкции и наоборот, то алгоритмы меняются местами.

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

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

_02Л_Законы АЛ

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

Законы де моргана для трех переменных

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

Читайте также:  Звукоизоляция для домашней студии

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

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

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

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

Для простоты записи приведем основные законы алгебры логики для двух логических переменных А и В. Эти законы распространяются и на другие логические переменные.

8. Законы склеивания: 9.

Упрощение логических выражений

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

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

Теорема поглощения записывается в двух формах — дизъюнктивной и

Докажем первую теорему. Вынесем за скобки букву А:

А +АВ= А(1 + В)

Согласно теореме (3) 1 + В = 1, следовательно

Чтобы доказать вторую теорему, раскроем скобки:

А(А + В) = А • А + АВ = А + АВ

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

Рассмотрим несколько примеров на применение теоремы поглощения при

упрощении булевых формул.

Теорема склеивания также имеет две формы — дизъюнктивную и

Докажем первую теорему:

поскольку согласно теоремам (5) и (4)

Для доказательства второй теоремы раскроем скобки:

Согласно теореме (6) следовательно:

По теореме поглощения (16) А+АВ = А

Теорема поглощения, как и теорема склеивания, применяется при упрощении

булевых формул, например:

Теорема де Моргана связывает все три основные операции булевой алгебры

— дизъюнкцию, конъюнкцию и инверсию:

Первая теорема читается так: инверсия конъюнкции есть дизъюнкция

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

Теорема де Моргана применима и к большему числу переменных:

Лекция 5

Инвертирование сложных выражений

Теорема де Моргана применима не только к отдельным конъюнкциям

или дизъюнкциям, но и к более сложным выражениям.

Найдем инверсию выражения АВ + CD,представленного в виде дизъюнкции конъюнкций. Инвертирование будем считать законченным, если знаки отрицания стоят только над переменными. Введем обозначения: АВ = Х;

Найдем и подставим в выражение (22):

Рассмотрим выражение, представленное в конъюнктивной форме:

(А + В)(С + D)

Найдем его инверсию в виде

Введем обозначения: А + В = X; С + D =Y,тогда

Найдем и подставим их в выражение

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

Понятие булевой функции

Вобщем случае функция (лат. functio — исполнение, соответствие,

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

под которым понимается область значений зависимого переменного f. В случае булевых функций X = F = <0,1>. Правилом, при помощи которого задается функция, может служить любая булева формула, например:

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

Аргументы — это независимые переменные, они могут принимать любые значения — либо 0, либо 1. Функция же f — зависимая переменная. Ее значение полностью определяется значениями переменных и логическими связями между ними.

Читайте также:  Записать iso на флешку exe

Главная особенность функции: чтобы определить ее значение, в общем случае необходимо знать значения всех аргументов, от которых она зависит. Например, приведенная выше функция зависит от трех аргументов А, В, С.Если принять А = 1, то получим

т. е. получилось новое выражение, не равное ни нулю, ни

единице. Пусть теперь В= 1. Тогда

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

Примем, наконец, С= 0. Тогда получим: f =0. Таким образом, если в исходном выражении принять А = 1, В= 1, С=0, то функция примет нулевое значение: f = 0.

Рассмотрим понятие набора значений переменных.

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

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

Например, если

то согласно латинскому алфавиту первым является аргумент Р, вторым —

Q, третьим — X, четвертым — У. Тогда по набору значений аргументов легко

найти значение функции. Пусть, например, дан набор 1001. Согласно его

записи т. е. на наборе 1001 заданная функция равна единице.

Еще раз отметим, что набор значений аргументов — это совокупность

нулей и единиц. Двоичные числа также являются наборами нулей и единиц.

Отсюда возникает вопрос — нельзя ли наборы рассматривать как двоичные

числа? Можно, и во многих случаях это очень удобно, особенно если двоичное

число перевести в десятичную систему. Например, если

А = 0, В = 1, С = 1, D=0,

то набор примет вид 0110. Если его считать двоичным числом, то:

т. е. заданный набор имеет номер 6 в десятичной системе.

Если по десятичному номеру требуется найти значения аргументов, то

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

Пусть, например, требуется найти значения аргументов А, В, С, D, Е, Fпо набору с номером 23. Переводим число 23 в двоичную систему методом

В результате получаем 2310 = 101112. Это число пятизначное, а всего

аргументов шесть, следовательно, слева необходимо записать один нуль:

2310 = 0101112. Отсюда находим:

А = 0, В = 1, С = 0, D = 1, Е = 1, F = 1.

Сколько всего существует наборов, если известно число п аргументов? Очевидно, столько же, сколько существует n-разрядных двоичных чисел, т. е. 2 n

Лекция 6

Задание булевой функции

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

На примере функции

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

Функция зависит от трех аргументов А, В, С. Следовательно, в таблице

предусматриваем три колонки для аргументов A,B,C и одну колонку для значений функции f. Слева от колонки А полезно разместить еще одну колонку. В ней будем записывать десятичные числа, которые соответствуют наборам, если их рассматривать как трехразрядные двоичные номера. Эта десятичная

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

ею можно пренебречь.

Заполняем таблицу. В строке с номером ООО записано:

А = В = С = 0.

Определим значение функции на этом наборе:

В колонке f записываем нуль в строке с набором 000.

Следующий набор: 001, т. е. А = В = 0, С = 1. Находим значение функции

На наборе 001 функция равна 1, следовательно, в колонке f в строке с

номером 001 записываем единицу.

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

Оцените статью
Adblock detector