Site Loader

Содержание

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

Что такое алгебра логики

Определение

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

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

Определение

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

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

Пример

Сегодня идет дождь.

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

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

 

Закон тождества

Теорема представлена в виде формулы: A=A.

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

Пример

«Движение – жизнь, а утренняя пробежка тоже является движением. Значит, утренняя пробежка – это жизнь». Рассуждение приводит к логически неверному итогу, поскольку в первом случае слово «движение» философского смысла, во втором – физического (буквально «перемещение в пространстве»).

Закон непротиворечия

Записывается в виде: \(A\&Ā=0\)

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

Пример

Бизнес несет убытки или не несет.

Закон исключенного третьего применяется только в определенных рассуждениях, где стоит формулировка «или –или».

Пример

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

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

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

Записывается в виде \(\overset=A=A\)

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

Пример

Шторы – элемент декора окон. Неверно, что шторы не являются элементом декора окон.

Свойства констант

Отрицание лжи есть истина:

\(A\cup0=A\)

\(A\cup1=1\)

Отрицание истины есть ложь:

\(A\&0=0\)

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

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

В записи данный закон выглядит так:

\(A\cup A=A\)

\(A\&A=A\)

Пример

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

Закон коммутативности

Рассматриваемая теорема применяется для выражений, связанных союзами «и», «или». Перемена мест высказываний в них не влияет на результат рассуждения.

\(A\cup B=B\cup A\)

\(А\&В=В\&А\)

Пример

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

Закон ассоциативности

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

\(A\cup(B\cup C)=(A\cup B)\cup C\)

\(А\&(В\&C)=(A\&В)\&С\)

Законы дистрибутивности

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

Дистрибутивность логического сложения относительно логического умножения имеет значение – А или (В и С) есть тоже самое, что А или В и А или С – и записывается формулой:

\(A\cup(B\&C)=(A\cup B)\&(A\cup C)\)

Дистрибутивность логического умножения над логическим сложением читается как – А и (В или С) есть тоже самое, что А и В или А и С – и имеет вид:

\(А\&(B\cup C)=(A\;\&\;B)\cup(А\&C)\)

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

Теорема, при которой верны следующие равенства:

  • для конъюнкции

\(A\cup(A\&B)=A\)

  • для дизъюнкции

\(A\&(A\cup B)=A\)

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

Законы общей инверсии названы в честь английского логика Августа де Моргана. Теорема для конъюнкции читается как – отрицание суждения «А и В» эквивалентно суждению «не-А или не-В» – и выглядит так:

\(\overline{A\&B}=\overline A\cup\overline B\)

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

\(\overline{A\cup B}=\overline A\&\overline B\)

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

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

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

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

 

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

Пример  

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • конъюнкция или логическое умножение;
  • дизъюнкция или логическое сложение;
  • инверсия или логическое отрицание.

Конъюнкция

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

Конъюнкция может быть записана следующими способами:

  • A и B;
  • A ⊥ B;
  • A ⋅ B;
  • A & B.
Пример

А – «Закончился дождь». B – «Из-за туч выглянуло солнце». Новое суждение «Закончился дождь, и из-за туч выглянуло солнце» является истиной только тогда, когда обе его части – А и B – истинны.

Дизъюнкция

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

Графическое обозначение дизъюнкции:

  • A или B;
  • A ⊦ B;
  • A|B;
  • A+B.
Пример

A – «В парке можно покататься на роликах»; B – «В парке можно просто погулять». Новое суждение «В парке можно покататься на роликах или просто погулять» будет ложным, есть и A, и B ложны.

Инверсия

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

Символическое представление:

Пример

A – «За окном бушует вьюга». Ā – «Неверно, что за окном бушует вьюга».

Разложение в дизъюнкцию

Составление совершенных форм происходит по таблице истинности функции.

Правило для составления дизъюнкции конституент единицы: для каждой комбинации переменных, где функция истинна, записывается минтерм ранга n>, где переменные с нулевым значением в рассматриваемом наборе берутся с отрицанием. Все конъюнктивные термы объединяют дизъюнктивно. СДНФ для номеров N=1, 3, 6, 7:

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

Разложение в конъюнкцию

Правило составления конъюнкции конституент нуля по таблице истинности: для каждого набора переменных, где функция имеет ложное значение, записывают дизъюнктивный терм ранга n, в котором переменные с единичными значениями на данной комбинации берутся с отрицанием. Все макстермы объединяют конъюнктивно. СКНФ для номеров наборов N=0, 2, 4, 5:

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

Как составить таблицу истинности

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

  1. Определить число переменных функции.
  2. Посчитать, сколько всего операций в выражении.
  3. Учесть скобки и установить порядок выполнения логических операций.
  4. Узнать количество столбцов в таблице путем сложения количества переменных и числа операций.
  5. В шапке таблицы записать переменные и операции в установленном в п.3 порядке.
  6. Определить количество строк в таблице (без шапки) по формуле m=2n.
  7. Выписать комбинации входных переменных, представленных в виде целого ряда двоичных чисел от 0 до 2n−1 с разрядом n.
  8. Заполнить столбцы таблицы, последовательно совершая логические операции.
Пример

В выражении A&B две переменные и одна операции – конъюнкция. Количество столбцов для данного примера – 3:

Таблица истинности для A&B выглядит так:

 

Логика. Таблицы истинности. Законы алгебры логики

Тема: Логические основы ЭВМ

Урок 1: Логические функции и таблицы истинности

Мы закончили тему «Арифметические основы ЭВМ». Познакомились с системами счисления.

  • Какая система счисления применяется в компьютере? (двоичная)

  • Почему? (существует 2 устойчивых состояния: ток течет – ток не течет, напряжение высокое – низкое, участок магнитного диска намагничен – не намагничен, на лазерном диске «выпуклость» и «впадина», от которых луч лазера отражается – не отражается)

  • Как выполняются арифметические операции в двоичной с.с.? Сложить два числа (обращая внимание на «запоминание» переносов)

1 1 1

1001

+1011

10100

  • А как же эти действия выполняются в компьютере?! Неужели компьютер таким же образом считает 1+1=10, 0 пишем, 1 в уме. Где же и как компьютер пишет, как именно запоминает «в уме»? Наша задача разобраться в этом.

  • На какой элементной базе строились ЭВМ различных поколений? Сколько поколений ЭВМ существует? (4 поколения: I – на электронных лампах; II – на транзисторах; III – на микросхемах; IV – большие интегральные схемы, микропроцессоры). А еще раньше – были построены счетные машины на электромеханических реле (Марк-1). А еще ранее в 1823 году Ч.Бэббидж пытался построить ЭВМ на основе гидравлических систем.

Основоположником древнейшей науки ЛОГИКИ был великий древнегреческий ученый Аристотель.

Логика – это наука о формах и способах мышления.

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

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

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

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

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

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

Высказывание может быть либо истинным, либо ложным.

Например:

– высказывание «В нашем классе сейчас горит свет» – истинно.

– высказывание «Кошки умеют летать» – ложно (для нормальных кошек).

Высказывание «X>Y» истинно при одних значениях Х и Y и ложно при других значениях. Поэтому «X>Y» – высказыванием не является. Не являются высказыванием и вопрос «Который час?», и восклицание «Какая прелесть!».

Простые высказывания можно объединять в сложные с помощью связок.

х

0

1

1

0

Пусть есть высказывание х «В нашем классе сейчас горит свет». Оно истинно.

Построим отрицание этого высказывания с помощью связки НЕ: «В нашем классе сейчас не горит свет». Оно ложно.

Или высказывание «Кошки умеют летать». Оно ложно. Отрицание этого высказывания: «Кошки не умеют летать» — истинно.

Функция, которая строится с помощью частицы «НЕ» называется ОТРИЦАНИЕ или ИНВЕРСИЯ.

Обозначается y= или y= ¬ х

х

y

x&y

0

0

0

0

1

0

1

0

0

1

1

1

Есть два высказывания:

х: «Ручка состоит из корпуса»

у: «Ручка состоит из стержня»

Объединим эти высказывания связкой «И»: «Ручка состоит из корпуса и стержня». Рассмотрим таблицу истинности для этого сложного высказывания:

Функция, которая строится с помощью частицы «И» называется КОНЪЮНКЦИЯ или Логическое умножение.

Обозначается z= x&y или z= xy или z= xy

х

y

xVy

0

0

0

0

1

1

1

0

1

1

1

1

Рассмотрим другие два высказывания:

х: «На улице идет дождь»

у: «На улице идет снег»

Объединим эти высказывания связкой «ИЛИ»: «На улице идет дождь или снег». Рассмотрим таблицу истинности для этого сложного высказывания:

Функция, которая строится с помощью частицы «И» называется ДИЗЪЮНКЦИЯ или Логическое сложение.

Обозначается z= xy z= x+y

х

y

xy

0

0

1

0

1

1

1

0

0

1

1

1

Рассмотрим еще два высказывания:

х: «На улице идет дождь»

у: «Улицы мокрые»

Объединим эти высказывания связкой «ЕСЛИ … ТО …»: «Если на улице идет дождь, то улицы мокрые». Рассмотрим таблицу истинности для этого сложного высказывания:

Функция, которая строится с помощью связки «ЕСЛИ … ТО …» называется ИМПЛИКАЦИЕЙ.

Обозначается z= xy

х

y

xy

0

0

1

0

1

0

1

0

0

1

1

1

Рассмотрим следующие два высказывания:

х: «Вася выучит уроки»

у: «Рак на горе свиснет»

Объединим эти высказывания связкой «ТОГДА И ТОЛЬКО ТОГДА …»: «Вася выучит уроки тогда и только тогда, когда рак на горе свиснет». Рассмотрим таблицу истинности для этого сложного высказывания:

Функция, которая строится с помощью связки «ТОГДА И ТОЛЬКО ТОГДА …» называется ЭКВИВАЛЕНТНОСТЬЮ.

Обозначается z= xy; x~y; x≡y;

х

y

xy xy

0

0

0

0

1

1

1

0

1

1

1

0

Рассмотрим еще два высказывания:

х: «На футбольном матче я сижу на северной трибуне»

у: «На футбольном матче я сижу на южной трибуне»

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

Функция, которая строится с помощью связкой «ЛИБО … ЛИБО …» называется СТРОГОЙ ДИЗЪЮНКЦИЕЙ или СЛОЖЕНИЕМ ПО МОДУЛЮ ДВА.

Обозначается z= xy или z= xy

Порядок выполнения логических операций (в порядке убывания приоритета их выполнения):

  1. Действия в скобках

  2. Инверсия ()

  3. Конъюнкция ( или &)

  4. Дизъюнкция ()

  5. Строгая дизъюнкция (сложение по модулю два) ( или )

  6. Импликация ()

  7. Эквивалентность ()

Задание 1: Построить таблицу истинности для функции:

х  y  x (y)

Решение:

  1. Определяем количество переменных (2: x и y)

  2. Определяем количество наборов (комбинаций 0 и 1 для такого количества переменных равно 2n, где n – количество переменных, в нашем случае n = 2: 22=4)

  3. Определяем порядок выполнения действий:

1 4 3 2

(х  y)  x (y)

  1. Составляем таблицу и заполняем ее:

y

1

(х  y)

2

(y)

3

x (y)

4

(1)(3)

0

0

1

1

1

1

0

1

1

0

1

1

1

0

0

1

1

1

1

1

1

0

0

1

Задание 2: Построить таблицу истинности для функции:

х (y)  z  x

Решение:

  1. Определяем количество переменных (3: x,y и z)

  2. Определяем количество наборов (2n для n = 3: 23=8)

  3. Определяем порядок выполнения действий:

2 1 3 4

х (y)  z  x

  1. Составляем таблицу и заполняем ее:

y

z

1

y

2

х  (y)

3

x (y) z

4

(3)(x)

2-й способ

х

y

z

3

x (y) z

4

(3)(x)

0

0

0

1

0

0

0

0

0

0

0

0

0

0

1

1

0

0

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

0

0

0

0

1

1

0

0

0

0

0

1

1

0

0

1

0

0

1

1

0

1

1

0

0

0

1

1

0

1

1

1

1

1

1

0

1

1

1

1

1

0

0

0

0

1

1

1

0

0

1

1

1

1

0

0

0

1

1

1

1

0

1

Покажем, как можно упростить построение таблицы истинности для этой функции: функция конъюнкция («И», логическое умножение) будет иметь значение 1, когда равны 1 все переменные, т.е. х=1, =1 (т.е. у=0) и z=1. Т.о. можно сразу же записать столбец 3:

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

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

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

  1. Выучить все функции, слова-связки, которые им соответствуют, их таблицы истинности.

  2. Построить таблицы истинности для следующих функций:

(х  y  z)  x

(х  y)  (y  z)

Урок 2: Преобразование логических выражений. Законы алгебры логики.

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

  1. Переместительный (коммутативный) закон

X v Y = Y v X; X & Y = Y & X

  1. Сочетательный (ассоциативный) закон

X v (Y v Z) = (X v Y) v Z; X & (Y & Z) = (X & Y) & Z

  1. Распределительный (дистрибутивный) закон

X & (Y v Z) = X & Y v X & Z

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

X v (Y & Z) = (X v Y) & (X v Z) (! Докажите этот закон с помощью таблиц истинности!)

  1. Операции с константами:

X  0 = X; X  1 = 1

X & 1 = X; X & 0 = 0

  1. Операции с переменной и ее инверсией (отрицанием)

X v = 1 — исключение третьего (Х  Х = 1)

X & = 0 — противоречие (Х  Х = 0)

  1. Двойное отрицание = Х ((Х) = Х)

  1. Правила де Моргана (чтобы “разбить” “длинную” инверсию, нужно поставить инверсии над каждой переменной, входящей в операцию, а знак операции изменить на противоположный). _____ _ _ ______ _ _

X v Y = X & Y; X & Y = X v Y

[ (X  Y) = X  Y; (X  Y) = X  Y ]

(! Докажите эти законы с помощью таблиц истинности!)

  1. Идемпотентность (убрать лишнее)

X v X = X; X & X = X

  1. Поглощение X v (X & Y) = X; X & (X v Y) = X

  1. Дополнительные формулы

A B = ¬ A B или в других обозначениях A B =

A ~ B = (¬ A B) ( A ¬B) = (¬ A ¬B) ( A B)
или в других обозначениях A B =

(т.к. )
(т.к. )

Задача: упростить выражение:

  1. Применяем закон де Моргана:

  2. 2-й раз применяем закон де Моргана:

  3. Снова применяем закон де Моргана для каждой «длинной» инверсии:

  4. Применяем закон двойного отрицания для b и c:

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

2-й способ решения данной задачи:

  1. Применяем закон де Моргана для конъюнкции (умножения):

  2. Применяем закон де Моргана для 1-й скобки и закон двойного отрицания для 2-й скобки:

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

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

  1. Выучить все законы алгебры логики.

  2. Доказать распределительный закон и 2 правила де Моргана с помощью таблиц истинности

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

Алгебра логики. Таблицы истинности — презентация онлайн

Алгебра логики.
Таблицы истинности
Основные понятия
Логические операции
Таблицы истинности
Примеры
Законы алгебры логики
Завершить показ
Основные понятия
Алгебра логики — это раздел математики, изучающий
высказывания, рассматриваемые со стороны их логических
значений (истинности или ложности) и логических операций
над ними.
Алгебра логики возникла в середине ХIХ века в трудах
английского математика Джорджа Буля. Ее создание
представляло собой попытку решать традиционные логические
задачи алгебраическими методами.
Логическое высказывание — это любое повествовательное
предложение, в отношении которого можно однозначно сказать,
истинно оно или ложно.
Основные понятия
Примеры:
1) предложение «6 — четное число» следует считать
высказыванием, так как оно истинное.
2) предложение «Рим — столица Франции» тоже
высказывание, так как оно ложное.
Разумеется, не всякое предложение является логическим
высказыванием. Высказываниями не являются, например,
предложения «ученик десятого класса» и «информатика —
интересный предмет». Первое предложение ничего не
утверждает об ученике, а второе использует слишком
неопределённое
понятие
«интересный
предмет».
Вопросительные и восклицательные предложения также не
являются высказываниями, поскольку говорить об их
истинности или ложности не имеет смысла.
Логические операции
Алгебра логики рассматривает любое высказывание только с
одной точки зрения — является ли оно истинным или ложным.
Высказывания, образованные из других высказываний с
помощью
логических
связок,
называются
сложными
(составными). Высказывания, не являющиеся составными,
называются простыми (элементарными).
Истинность или ложность получаемых таким образом составных
высказываний зависит от истинности или ложности элементарных
высказываний.
Значение логических операций задается через таблицы
истинности. В этих таблицах для всех возможных значений
высказываний указываются результаты соответствующей
логической операции (истинна кодируется 1, ложь кодируется 0).
Каждая логическая связка рассматривается как операция над
логическими высказываниями и имеет свое название и обозначение.
Логические операции
Операция
НЕ
(отрицание)
Логическая операция, при которой высказывание истинно,
когда исходное высказывание ложно, и ложно, когда исходное
высказывание — истинно, называется отрицанием.
Обозначается чертой над высказыванием (например, A ).
Операция логического отрицания применима к одному
высказыванию. Приведем таблицу истинности для логической
операции отрицание:
A
F A
0
1
1
0
Логические операции
Операция
ИЛИ
(логическое сложение, дизъюнкция)
Дизъюнкция — логическая операция, имеющая значение
«истина», если истинно хотя бы одно из составляющих
высказываний и имеющая значение «ложь», если ложны все
высказывания
Обозначается знаком (например, A B ).
Операция логическое ИЛИ применима к двум
высказываниям и определяется следующей таблицей
истинности:
A
B
F=A B
0
0
0
0
1
1
1
0
1
1
1
1
Логические операции
Операция
И
(логическое умножение, конъюнкция)
Конъюнкция — логическая операция, имеющая значение
«истина», если истинны все высказывания и имеющая
значение «ложь», если ложно хотя бы одно из составляющих
высказываний.
Обозначается знаком & (например, A & B ).
Операция логическое И применима к двум высказываниям
и определяется следующей таблицей истинности:
A
B
F=A&B
0
0
0
0
1
0
1
0
0
1
1
1
Примеры.
№1 Построить таблицу истинности для высказывания
F A& B
Решение:
A
B
B
F A& B
0
0
1
0
0
1
0
0
1
0
1
1
1
1
0
0
Примеры.
№2 Определить истинно или ложно составное
высказывание:
«(3 5=15 и 7 12=94) или (3 7=18 или 8 11=88)»
Решение:
Запишем высказывание в виде (учитываем истинное
высказывание кодируем 1, ложное – 0; логические операции
или — , и — &)
(1 & 0) (0 1)=0 1=1
Ответ: составное высказывание истинно
Законы алгебры логики
В алгебре логики выполняются следующие основные законы:
1) закон коммутативности:
A& B B & A
A B B A
2) закон ассоциативности:
A & B & C A & B & C
A B C A B C
3) закон дистрибутивности:
A & B C A & B A & C
A B & C A B & A C
Законы алгебры логики
4) закон поглощения 0 и 1:
A 0 A
A &1 A
5) закон противоречия:
A& A 0
6) закон исключенного третьего:
A A 1
7) закон двойного отрицания:
8) закон поглощения :
A A
A A & B A
A & A B A

Урок информатики по теме «Алгебра логики. Законы логики. Упрощение логических выражений» | План-конспект урока по информатике и икт (9 класс):

Слайд 1

Домашнее задание Задание . Построить таблицы истинности для выражений: (А  В) и  А   В. Подготовиться к самостоятельной работе.

Слайд 2

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

Слайд 3

Задание 3. Составить таблицу истинности для заданного выражения А  (В  С ) A B C В  С А  (В  С) Посчитать количество необходимых строк в таблице: 2. Посчитать количество необходимых столбцов: Кол-во столбцов = количество логических переменных + кол-во логических операций.

Слайд 4

3. Заполнить шапку таблицы логическими переменными и операциями . Порядок действий: 1. Действия в скобках. 2. Отрицание. 3. Логическое умножение. 4. Логическое сложение. 4. Заполнить таблицу значениями ее исходных переменных. A B C (В  С) А  (В  С) 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

Слайд 5

5. Выполнить базовые логические операции в определенной последовательности на основании таблиц истинности логических операций. A B C (В  С) А  (В  С) 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

Слайд 6

Задание № 1 А  ( В  С) А В С В  С А  (В  С) 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 0 0 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1

Слайд 7

(А  В)  (A  С ) А В С А  В А  С (А  В)  (A  С ) 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 1 0 1 0 1 1 1 1 0 1 0 1 1 1 1 1 1 1 Задание № 2

Слайд 8

Алгебра логики. Законы логики. Упрощение логических функций

Слайд 9

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

Слайд 10

Законы исключения констант 0=1 1=0 А0=А А  0= 0 А 1 = 1 А 1 =А Задание №2. Упростить:  ( А  1 )

Слайд 11

Законы алгебры логики Идемпотентность АА=А А  А=А Коммутативность – переместительный закон А  В = В  А А  В=В  А Ассоциативность – сочетательный закон А  (В  С) = (А  В)  С А  (В  С) = (А  В)  С Дистрибутивность – распределительный закон А  (В  С) = (А  В)  (A  С ) А  (В  С) = (А  В)  (A  С )

Слайд 12

Задание № 3. Расставьте соответствие между названием закона логики и номером выражения, к которому он был применен 1. Идемпотентность. 2. Дистрибутивность. 3. Ассоциативность. 4. Коммутативность. C  ( V  N ) = ( C  V )  (C  N) . (B  C)  P = (C  B)  P. (M  N)  ( K  L) = M  (N  K)  L. (B  B)  P = B  P.

Слайд 13

Поглощение А  (А  В) = А А  (А  В) = А Законы де Моргана (инверсии)  (А В) =  А  В  (А  В) =  А   В З акон исключения (склеивания) (А  В)  (A  В ) =А (А  В)  (A  В ) =А

Слайд 14

Задание № 4. Упростить выражения, используя законы логики  (  X   Y ) . ( А  В )  ( А   В ). C  (B  C).

Слайд 15

Задание № 5. Найдите значение логического выражения : ((1 ˄ 1) ˄ (0 ˅ 1)) ˅ ¬0 ), ((0 ˅ 1) ˅ (1˄1)) ˅ (0 ˅ 1 ).

Слайд 16

А  (¬(¬В  С))=??? ¬ ( А  ¬ В  ¬ С)=??? Задание № 6. Упростите логическое выражение

Слайд 17

Домашнее задание Подготовиться к контрольной работе по изученному материалу

Лекция по информатике «Алгебра логики»

10

Лекция № 6

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

Построение таблиц истинности сложных высказываний

1. Формы мышления

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

Логика – это наука о формах и способах мышления.

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

Мышление всегда осуществляется в каких-то формах. Основными формами мышления являются:

1) Понятие

Понятие — это форма мышления, фиксирующая основные, существенные признаки объекта.

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

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

Объем понятия определяется совокупностью предметов, на которые оно распространяется. Объем понятия «персональный компьютер» выражает всю совокупность (сотни миллионов) существующих в настоящее время в мире персональных компьютеров.

2) Высказывание

Высказывание — это форма мышления, в которой что-либо утверждается или отрицается о реальных предметах, их свойствах и отношениях между ними. Высказывание может быть либо истинно, либо ложно (5 + 3 = 8 – истинное высказывание; Лондон является столицей Франции – ложное высказывание).

Высказывание не может быть выражено повелительным, восклицательным, или вопросительным предложением, т. к. оценка их истинности или ложности невозможна.

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

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

Приведенное выше составное высказывание истинно, т.к. истинны, входящие в него простые высказывания.

3) Умозаключение

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

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

2. Понятие об алгебре высказываний

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

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

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

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

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

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

А — «два умножить на два равно четырем»,

В — «два умножить на два равно пяти».

Высказывания, как уже говорилось ранее, могут быть истинными или ложными. Истинному высказыванию соответствует значение логической переменной 1, а ложному — значение 0. В нашем случае первое высказывание истинно (А = 1), а второе ложно (В = 0).

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

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

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

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

Из этого следует два вывода:

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

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

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

3. Основные логические операции

Логическое умножение (конъюнкция)

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

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

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

Перейдем теперь от записи высказываний на естественном языке к их записи на формальном языке алгебры высказываний (алгебры логики). Операцию логического умножения (конъюнкцию) принято обозначать либо значками «&», «» либо знаком умножения «*». Образуем составное высказывание F, которое получится в результате конъюнкции двух простых высказываний:

С точки зрения алгебры высказываний мы записали формулу функции логического умножения, аргументами которой являются логические переменные А и В, которые могут принимать значения «истина» (1) и «ложь» (0).

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

По таблице истинности легко определить истинность составного высказывания, образованного с помощью операции логического умножения. Рассмотрим, например, составное высказывание «2х2=4 и 3х3=10». Первое простое высказывание истинно (А = 1), а второе высказывание ложно (В = 0), по таблице определяем, что логическая функция принимает значение ложь (F = 0), т.е. данное составное высказывание ложно.

А

В

1

1

1

1

0

0

0

1

0

0

0

0

Логическое сложение (дизъюнкция)

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

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

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

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

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

По таблице истинности легко определить истинность составного высказывания образованного с помощью операции логического сложения. Рассмотрим, например, составное высказывание «2х2=4 или 3х3=10». Первое простое высказывание истинно (А = 1), а второе высказывание ложно (В = 0), по таблице определяем, что логическая функция принимает значение истина (F = 1), т.е. данное составное высказывание истинно.

А

В

1

1

1

1

0

1

0

1

1

0

0

0

Логическое отрицание (инверсия)

Присоединение частицы «не» к высказыванию называется операцией логического отрицания или инверсией.

Логическое отрицание (инверсия) делает истинное высказывание ложным и, наоборот, ложное — истинным.

Пусть А = «Два умножить на два равно четырем» — истинное высказывание, тогда высказывание F, образованное с помощью операции логического отрицания, «Два умножить на два не равно четырем» -ложно.

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

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

Истинность высказывания, образованного с помощью операции логического отрицания, можно легко определить с помощью таблицы истинности. Например, высказывание «Два умножить на два не равно четырем» ложно (А = 0), а полученное из него в результате логического отрицания высказывание «Два умножить на два равно четырем» истинно (F = 1).

А

1

0

0

1

Логическое следование (импликация)

А

В

1

1

1

1

0

0

0

1

1

0

0

1

Логическое равенство (эквиваленция)

А

В

1

1

1

1

0

0

0

1

0

0

0

1

Порядок следования логических операций

отрицание (, конъюнкция (, дизъюнкция (, импликация (, эквиваленция (

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

Построение таблиц истинности составных высказываний

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

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

Запишем в форме логического выражения составное высказывание «2х2=5 или 2х2=4 и 2х25 или 2х24». Проанализируем составное высказывание. Оно состоит из двух простых высказываний:

А = «2х2=5» — ложно (0),

В = «2х2=4» — истинно (1).

Тогда составное высказывание можно записать в следующей форме:

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

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

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

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

При построении таблиц истинности целесообразно руководствоваться определенной последовательностью действий.

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

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

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

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

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

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

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

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

Таблицы истинности совпадают, следовательно, логические выражения равносильны:

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

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

  2. определить число строк в таблице, которое равно Q = 2n

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

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

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

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

Переменные

Промежуточные логические формулы

Формула

x

y

z

0

0

0

1

1

0

1

0

0

0

0

1

1

1

0

1

1

1

0

1

0

0

0

1

1

0

1

0

1

1

0

0

1

1

1

1

1

0

0

1

1

0

0

0

0

1

0

1

1

1

0

0

0

0

1

1

0

0

1

0

0

0

0

1

1

1

0

1

0

0

0

0

Пример (см. выше):

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

Логические элементы эвм. алгебра логики. законы алгебры логики.

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

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

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

Совокупность значений логических переменных x1, x2, …, xn называется набором переменных.

Общее число ФАЛ n переменных определяется возведением числа 4 в степень n, т. е. 4n. Существуют четыре ФАЛ одной логической переменной.

Функции F0(х) = 0 и F3(х) = 1 являются константами (функции не изменяются при изменении аргумента). Функция F1(х) = х повторяет значение аргумента х. Функция F2(x) называется отрицанием переменной или инверсией и обозначается так:

F2(x) = .

Из оставшихся десяти логических функций широкое распространение имеют функции F1(х) (конъюнкцияилилогическое умножение) и F7(х) (дизъюнкцияилилогическое сложение), которые совместно с функцией инверсии составляют функционально полную систему логических функций. С помощью этих трех функций можно представить (аналитически выразить) любую сколь угодно сложную логическую функцию. Очень важной для вычислительной техники является логическая функция исключающее ИЛИ (неравнозначность, сложение по модулю два). Функция исключающее ИЛИ обозначается символом A. Ниже приведены таблицы истинности для этих трех функций.

Инверсия
х
x2 x1 x2 U x1 x2 U x1 x2A x1

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

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

Кодирование информации. Кодовая таблица. Система кодирования ASCII. Система кодирования UNICODE.

Кодирование информации— это процесс формирования определенного представления информации.

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

Кодовая таблица

в кодовой таблице представлено определенное количество строк и только два столбца:

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

Определение

Кодовая таблица — это совокупность цифровых (двоичных) кодов и их значений.

Самая распространенная система кодирования латиницы — ASCII — использует 7 бит на символ. Другие алфавиты обычно кодируются более сложным образом.Используются две основные кодировки латиницы — ASCII и EBCDIC (Extended Binary Coded Decimal Information Code), применяемая системами AS/400, System/370, System/390 и z90 фирмы IBM. Операции сравнения в современных процессорах реализованы как неразрушающее вычитание — мы производим те же действия, что и при обычном двоичном вычитании, но запоминаем не сам результат, а лишь флаги знака, переноса и равенства результата нулю. На основании значений этих флагов определяем результат сравнения: если разность равна нулю, сравниваемые символы одинаковы, если она положительна или отрицательна, один из символов больше или меньше другого.
В кодировке ASCII (American Standard Code for Information Interchange — Американский стандартный код обмена информацией), например, все символы латиницы, цифры и большинство распространенных знаков препинания обозначаются кодами от 0 до 127, при этом коды букв расставлены в соответствии с латинским алфавитом. В США, как и в других англоязычных странах, латинский алфавит используется в неизмененном виде, а для передачи звуков, отсутствовавших в оригинальном латинском языке, применяется причудливая орфография. Большинство других европейских алфавитов обходит проблему несоответствия фонетик путем расширения набора символов латиницы — например, в немецком языке добавлены буквы o, a, u и ?. Другие языки имеют множество различных акцентов и диакритических символов, расставляемых над буквами для указания особенностей произношения.itatx eto po-russki, smenite kodirovku). Естественно, совместить такое сопоставление и алфавитную сортировку невозможно.
Стандартным решением в таких случаях является использование для сравнения и лексикографической сортировки промежуточных таблиц, в которых для каждого допустимого кода указан его номер в лексикографическом порядке. На уровне системы команд процессоры этого обычно не делают, но на уровне библиотек языков высокого уровня это осуществляется очень часто.

Статьи к прочтению:

Элемент Музыка


Похожие статьи:
  • Базовыми операциями алгебры логики

    операции логического умножения – конъюнкции ( ), логического сложения – дизъюнкции ( ), исключающего или – (A), логического отрицания – инверсии ( )….

  • Системы функций алгебры логики

    Рассмотрим теорему Жегалкина, которая играет важную роль в алгебре логики. Теорема Жегалкина. Любая булева функция может быть представлена многочленом…

Пешаварский университет

Автор (ы): Латиф-ур-Рахман, Анвар-уль-Хак Али Шах, Афзал Шах, Сайед Мухаммад Салман, Абдул Халик Янв
Год: 2022
Журнал: Biointerface Res. Прил. Chem.
Объем: 12
Выпуск: 1
Страниц: 377-390

Автор (ы): 2. Парвин, С., Л. Бадшах, А. Уллах, С.Г. Али, С.М. Шах, А. Заман и С. Х. Сиддики.
Год: 2021
Журнал: Этноботанические исследования и приложения
Том: 22
Выпуск: 30
Страниц: 1-16
Ссылка: Скачать

Автор (ы): 1. Аббас, К., С. Батул, С.В. Хан, А. Хуссейн, СУ Дин, М.А. Нафис, С. Али, М.А. Файзи и А.
Год: 2021
Журнал: Пакистанский журнал научных и промышленных исследований серии «Биологические науки»,
Том: 64
Выпуск: 3
Страниц: 251-255
Ссылка: Скачать

Автор (ы): Раис Хан, Башир Хан, Абдур Рашид, Асад Уллах и Шейх Заин Ул Абидин
Год: 2021
Журнал: Microscopy Research & Technique
Volume: 84
Выпуск: 12
Страниц: 1-7
Ссылка: Скачать

Автор (ы): Муджиб Ур Рахман, З.Мухаммад, Р. Уллах, В. М. Хан, А. Уллах, Т. Уллах, Х. Али, Г. Джелани и И. А.
Год: 2021
Журнал: Mitteilungen Klosterneuburg
Том: 71
Выпуск: 5
Страниц: 20-40
Ссылка: Скачать

Законы булевой алгебры | Учебник по организации и архитектуре компьютера

Основные законы булевой алгебры можно сформулировать следующим образом:

  • Закон коммутации гласит, что изменение порядка операндов в булевом уравнении не меняет его результат.Например:
    1. Оператор ИЛИ → A + B = B + A
    2. Оператор И → A * B = B * A
  • Ассоциативный закон умножения гласит, что операция И выполняется над двумя или более чем двумя переменными. Например:
    A * (B * C) = (A * B) * C
  • Закон распределения
  • гласит, что умножение двух переменных и сложение результата с переменной приведет к тому же значению, что и умножение сложения переменной с отдельными переменными. Например:
    A + BC = (A + B) (A + C).
  • Закон об аннулировании:
    A.0 = 0
    A + 1 = 1
  • Закон идентичности:
    A.1 = A
    A + 0 = A
  • Идемпотентный закон:
    A + A = A
    A.A = A
  • Закон дополнения:
    A + A ‘= 1
    A.A’ = 0
  • Закон двойного отрицания:
    ((A) ‘)’ = A
  • Закон поглощения:
    A. (A + B) = A
    A + AB = A

Закон Де Моргана, также известный как теорема Де Моргана, работает в зависимости от концепции двойственности. Двойственность утверждает, что перестановка операторов и переменных в функции, например замена 0 на 1 и 1 на 0, оператора AND на оператор OR и оператора OR на оператор AND.

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

  1. «Отрицание конъюнкции — это дизъюнкция отрицаний», что означает, что дополнение произведения двух переменных равно сумме дополнений отдельных переменных. Например, (A.B) ‘= A’ + B ‘.
  2. «Отрицание дизъюнкции — это соединение отрицаний», что означает, что дополнение суммы двух переменных равно произведению дополнения каждой переменной.Например, (A + B) ‘= A’B’.

1.2.4: Дополнительные правила булевой алгебры

Конечно, неверно, что все возможные правила булевой алгебры приведены на рис. 2.2. Во-первых, есть много правил, которые являются простым следствием правил, которые там перечислены. Например, хотя таблица утверждает только, что \ (\ mathbb {F} \ vee p \) p , также верно, что \ (p \ vee \ mathbb {F} \) p . Это можно проверить напрямую или простым вычислением:

\ (p \ vee \ mathbf {F} \ Equiv \ mathbf {F} \ vee p \ qquad \) Коммутативный закон

\ (\ Equiv p \ qquad \) Закон идентичности, как указано в таблице

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

Другой вид простого расширения может быть применен к ассоциативному закону ( p q ) ∨ r p ∨ ( q r ). Закон сформулирован для оператора ∨, применяемого к трем членам, но он обобщается на четыре или более терминов. Например

(( p q ) ∨ r ) ∨ s
≡ ( p q ) ∨ ( r s ) по ассоциативному закону для трех сроков

p ∨ ( q ∨ ( r s )) по ассоциативному закону для трех членов

Мы, конечно, часто будем писать это выражение как p q r s , без скобок вообще, зная, что где бы мы ни помещали круглые скобки, значение одно и то же.

Еще одна вещь, о которой вы должны помнить, — это то, что правила могут применяться в любом направлении. Распределительный закон, например, позволяет распределить p в p ∨ ( q ∧¬ p ), чтобы получить ( p q ) ∧ ( p ∨¬ p ). Но его также можно использовать в обратном порядке, чтобы « исключить » термин, например, когда вы начинаете с ( q ∨ ( p q )) ∧ ( q ∨ ( q p ) )) и вычлените q , чтобы получить q ∨ (( p q ) ∧ ( q p )).

До сих пор в этом разделе мы работали с законами булевой алгебры, не говоря особо о том, что они означают или почему они разумны. Конечно, вы можете применять законы в расчетах, не понимая их. Но если вы хотите выяснить, какие вычисления делать, вам нужно некоторое понимание. Большинство законов достаточно ясны, если немного подумать. Например, если мы уже знаем, что q ложно, тогда p q будет истинным, если p истинно, и ложным, если p ложно.То есть p ∨ F имеет то же логическое значение, что и p . Но об этом и говорится в Законе о личности ∨. Некоторые законы требуют дальнейшего обсуждения.

Закон исключенного среднего, p ∨ ¬ p ≡ T, гласит, что для любого предложения p по крайней мере одно из p или ¬ p должно быть истинным. Поскольку ¬ p истинно именно тогда, когда p ложно, это то же самое, что сказать, что p должно быть истинным или ложным.Там нет никакого среднего. Закон противоречия, p ∧ ¬ p ≡ F, гласит, что оба утверждения p и ¬ p не могут быть истинными. Оба эти правила очевидны.

Есть некоторые, кто ставит под сомнение закон отсутствия золотой середины. Уже в 1920-х годах такие люди, как Тарский (с которым мы встретимся позже), говорили о других формах логики, в которых также существует другое значение, представляющее «неизвестное» или «не доказанное». Вы также можете увидеть это в некоторых языках программирования, где они называются «логическими значениями с тремя состояниями».

Эти так называемые нестандартные логики были разработаны и также привели к таким вещам, как «нечеткая логика», которые некоторые считают весьма спорными. Лотфи Заде считается первым человеком, который назвал этот тип логики нечеткой логикой в ​​своей работе над «нечеткими множествами» в 1965 году. Позднее Заде был процитирован как сказал: «Не бояться разразиться спорами. … Это тоже часть моего характера. Я могу быть очень упрямым. Вероятно, это было полезно для развития Fuzzy Logic.”

Источник: en.Wikipedia.org/wiki/Lotfi_A._Zadeh

Законы распределения нельзя назвать очевидными, но несколько примеров могут показать, что они разумны. Рассмотрим утверждение: «Эта карта — туз пик или треф». Ясно, что это эквивалентно «Эта карта — туз пробелов или эта карта — туз треф». Но это всего лишь пример первого закона распределения! Ибо пусть a представляет предложение

«Эта карта — туз», пусть s обозначает «Эта карта — пика», а c обозначает «Эта карта — клуб».Тогда «Эта карта — туз пик или треф» можно перевести в логику как a ∧ ( s c ), а «Эта карта — туз пик или эта карта — туз пик. клубы »становится ( a s ) ∨ ( a c ). А закон распределения гарантирует нам, что a ∧ ( s c ) ≡ ( a s ) ∨ ( a c ). Второй закон распределения говорит нам, например, что «Эта карта — либо джокер, либо бубновая десятка» логически эквивалентна «Эта карта — либо джокер, либо десятка, и это eitherajokeroradiamond».То есть j ∨ ( t d ) ≡ ( j t ) ∧ ( j d ). Законы распределения — мощные инструменты, и вы должны помнить о них всякий раз, когда сталкиваетесь со смесью операторов ∧ и ∨.

Законы ДеМоргана также не должны быть очевидными, поскольку люди часто ошибаются. К счастью, вы можете практиковать их как в «Рассуждении и логике», так и в «Компьютерной организации», так что скоро вы поймете их правильно. Что еще более важно, возможно, они тоже имеют смысл.Рассматривая ¬ ( p q ), вы должны спросить себя, как могут « p и q » не соответствовать действительности. Это не будет истинным, если либо p ложно, либо если q ложно (или оба). То есть ¬ ( p q ) эквивалентно (¬ p ) ∨ (¬ q ). Рассмотрим предложение «Ворон большой и черный». Если птица не большая и черная, то это не ворон. Но что именно означает быть «не (большим и черным)»? Как вы можете определить, верно ли утверждение «не (большой и черный)»? Это будет верно, если он либо не большой, либо не черный.(Это не обязательно должно быть и то, и другое — оно может быть большим и белым, оно может быть маленьким и черным.) Точно так же, если « p или q » не может быть истинным, оба p и q должно быть ложным. То есть ¬ ( p q ) эквивалентно (¬ p ) ∧ (¬ q ). Это второй закон ДеМоргана.

Вспоминая, что p q эквивалентно (¬ p ) ∨ q , мы можем применить закон ДеМоргана, чтобы получить формулу для отрицания импликации:

¬ ( p q ) ≡ ¬ ((¬ p ) ∨ q )
≡ (¬ (¬ p )) ∧ (¬ q )

p ¬ ¬ q

То есть p q ложно именно тогда, когда и p истинно, и q ложно.Например, отрицание «Если у вас есть туз, вы выиграете», это «У вас есть туз, и вы не выиграете». Подумайте об этом так: если у вас был туз, но вы не выиграли, то утверждение «Если у вас есть туз, вы выиграете», то утверждение не соответствует действительности.

Упражнения

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

    q ).
    b) Постройте таблицы истинности, чтобы продемонстрировать, что ¬ ( p q ) логически не эквивалентно (¬ p ) ∨

    q ).
    c) Создайте таблицы истинности, чтобы продемонстрировать действительность обоих законов ДеМоргана.

  3. Постройте таблицы истинности, чтобы продемонстрировать, что ¬ ( p q ) логически не эквивалентно любому из следующего.

    а) (¬ п ) → (¬ q ) б) (¬ п ) → q

    c) p → (¬ q )
    Вернитесь к этому разделу для получения формулы, которая логически эквивалентна ¬ ( p q ).

  4. Является ли ¬ ( p q ) логически эквивалентным (¬ p ) ↔ (¬ q )?
  5. В алгебре чисел существует распределительный закон умножения над сложением: x ( y + z ) = xy + xz . Как мог бы выглядеть распределительный закон сложения над умножением? Верно ли это в алгебре чисел?

6. Законы распределения приведены на Рисунке 2.2 иногда называют левыми законами распределения. Правильные законы распределения гласят, что ( p q ) ∧ r ≡ ( p r ) ∨ ( q r ) и что ( p q ) r ≡ ( p r ) ∧ ( q r ). Покажите, что правильные законы распределения также являются действительными законами булевой алгебры. (Примечание: на практике и левый, и правый законы распределения называются просто законами распределения, и оба могут свободно использоваться в доказательствах.)

7.Покажите, что p ∧ ( q r s ) ≡ ( p q ) ∨ ( p r ) ∨ ( p 9070 s ∧ ∧ ) для любых предложений p , q , r и s . На словах мы можем сказать, что союз распределяется по дизъюнкции трех членов. (Напомним, что оператор ∧ называется конъюнкцией, а ∨ — дизъюнкцией.) Переведите в логику и убедитесь, что конъюнкция распределяется по дизъюнкции четырех членов.Утверждают, что на самом деле конъюнкция распределяется по дизъюнкции любого числа терминов.

  1. Есть два дополнительных основных закона логики, включающих два выражения: p ∧ F и p T. Какие законы отсутствуют? Покажите, что ваши ответы на самом деле являются законами.
  2. Для каждой из следующих пар предложений покажите, что два предложения логически эквивалентны, найдя цепочку эквивалентностей от одного к другому. Укажите, какое определение или закон логики оправдывает каждую эквивалентность в цепочке.
  3. Для каждого из следующих составных предложений найдите более простое предложение, которое логически эквивалентно. Постарайтесь найти максимально простое предложение.

    a) ( p q ) ∨ ¬ q b) ¬ ( p q ) ∧ p c) p → ¬ p
    d) ¬1 p p ∧ ( p q ) e) ( q p ) → q f) ( p q ) ∧ (¬ p q )

  4. Выразите отрицание каждого из следующих предложений на естественном английском языке: a) Это солнечно и холодно.

    б) У меня будет строопвафель или у меня будет аппелтаарт. В) Если сегодня вторник, это Бельгия.

    d) Если вы сдадите заключительный экзамен, вы пройдете курс.

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

    а) Я выпью кофе и вафель или аппелтаарт. Б) У него нет ни таланта, ни амбиций.

    c) У вас может быть олиболлен, или у вас может быть олиболлен.

  6. Предположим, что одновременно верно, что «Все лимоны желтые» и «Не все лимоны желтые». Сделайте вывод «Единороги существуют». (Если вы застряли, загляните на en.Wikipedia.org/wiki/ Principle_of_explosion.)

Булева алгебра

Булева алгебра

Логическая алгебра

Введение

При работе с логическими отношениями в цифровой форме нам понадобится набор правила символического манипулирования, которые позволят нам упростить сложные выражения и решите для неизвестных.Первоначально булева алгебра сформулировал Джордж Буль, английский математик (1815-1864) описал предложения, результат которых будет либо истина, либо ложь . В компьютерной работе используется в дополнение для описания схем, состояние которых может быть либо 1 (истина) или 0 (ложь) . Используя отношения, определенные в И, ИЛИ и НЕ эксплуатации, ряд постулатов изложен в таблице 2.1. [Ссылка 3].

  • P1: X = 0 или X = 1
  • P2: 0 0 = 0
  • P3: 1 + 1 = 1
  • P4: 0 + 0 = 0
  • P5: 1 1 = 1
  • P6: 1 0 = 0 1 = 0
  • P7: 1 + 0 = 0 + 1 = 1
Таблица 2.1 Логические постулаты


Основные булевы теоремы

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

Принцип двойственности 1. Замена операций OR и AND в выражении.
2. Меняем местами элементы выражения 0 и 1.
3. Не менять форму переменных.

Таблица 2.2 Теоремы булевой алгебры
T1: Коммутативный закон
(а) A + B = B + A
(б) A B = B A
T2: Ассоциативный закон
(а) (A + B) + C = A + (B + C)
(б) (А Б) С = А (В С)
T3: Закон о распределении
(a) A (B + C) = A B + A C
(б) А + (В С) = (А + В) (А + С)
T4: Закон о личности
(а) А + А = А
(б) A A = A
T5: Закон об отрицании
(a)
(b)
T6: Закон о резервировании
(а) A + A B = A
(б) А (А + В) = А
T7:
(а) 0 + A = A
(б) 1 А = А
(в) 1 + A = 1
(г) 0 A = 0
T8:
(а)
(б)
T9:
(a)
(b)
T10: Теорема Де Моргана
(а)
(б)

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


Пример 2.1 Доказательство T9: (a)

(1) Алгебраически,

(2) Используя таблицу истинности,

(3) Используя диаграммы Венна,


Пример 2.2 Нарисуйте принципиальную схему логического выражения :

Цепь:


Пример 2.3 Напомним определение логического элемента И-НЕ:

На выходе логического элемента И-НЕ высокий уровень, если на каком-либо из его входов низкий уровень. То есть выход низкий , только если все его входы высокий. Логическое выражение для логического элемента И-НЕ с 4 входами:


где Выход = 0, когда A = 1, B = 1, C = 1 и D = 1; Выход = 1 в противном случае.
Проблема 2.1

(a) Докажите T9 (b).

(b) Докажите T10: (a) и (b), заполнив таблицы истинности ниже:

Щелкните здесь, чтобы ознакомиться с типовым ответом.

Задача 2.2

(a) Запишите логическое выражение на выходе Y 3-входного Ворота NAND,

с точки зрения входов A, B и C.

(b) Заполните приведенную ниже таблицу истинности для схемы в (a). Щелкните здесь, чтобы ознакомиться с типовым ответом.

Перейти к следующей главе или Предыдущая глава или Домашняя страница

Булева алгебра — 2. Законы

законов булевой алгебры!

Live by the X. Die by the X.

Введение

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

Эти законы иногда также называют правилами булевой алгебры.

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

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

Булева коммутативность

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

a OR b = b OR a

Или с несколькими терминами:

a AND b AND c AND d = b AND d AND c AND a

Это также относится к части выражения в квадратных скобках:

a И (b ИЛИ C) = a И (c ИЛИ b)

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

x ИЛИ (y AND z) = (y и z) OR x

Коммутативность работает для любой операции, которая принимает два или более терминов (например, AND, OR, NOR, NAND, XOR).

Логическая идентичность

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

Член в операции ИЛИ с фиксированным значением Ложь приведет к члену:

г ИЛИ Неверно =

г

Аналогично, член в операции И с фиксированным значением ИСТИНА приведет к члену.

ч И Истинно = ч

Логический закон дополнения

Закон дополнения имеет отношение к соотношению между переменной (например, c) и отрицанием этой переменной (не (c)). Рассмотрим следующее выражение:

c ИЛИ НЕ (c) = Истина

Если c имеет значение False, тогда Not (c) должно быть True. Наоборот. В любом случае один из них всегда будет True, поэтому результат всегда будет True.

Альтернативно:

c AND NOT (c) = ложь

Принимая во внимание наблюдение выше, невозможно, чтобы c и Not (c) были True одновременно, поэтому это всегда будет False.

Логический идемпотентный закон

Этот закон связан с повторением переменной в выражении. Фактически это можно упростить до самого себя. Так например:

r ИЛИ r = r и r И r = r

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

Логический закон двойного отрицания

Этот закон также имеет смысл, если задуматься. Этот закон гласит, что если вы отрицаете отрицание (т. Е. Если у вас есть НЕ внутри НЕ), они эффективно нейтрализуют друг друга.

НЕ (НЕ (b)) = b

Первый НЕ переворачивает значение b, затем второй НЕ переворачивает его обратно.

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

НЕ (НЕ (d AND f)) = d AND f

Но

НЕ (НЕ (v) ИЛИ t) ≠ v ИЛИ t

Это потому, что внешнее НЕ применяется к НЕ (v) ИЛИ t , а внутреннее НЕ применяется только к v .Они применимы к разным частям выражения и не могут быть отменены.

Логическая ассоциативность

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

a OR b OR c = (a OR b) OR c = a OR (b OR c) = (a OR c) OR b

А:

a AND b AND c = (a AND b) AND c = a AND (b AND c) = (a AND c) AND b

Это также можно сделать для подходящей части выражения.Итак:

a AND (b OR c OR d) = a AND (b OR (c OR d))

Но если операторы смешаны, то этого может и не произойти.

a AND (b OR c) ≠ (a AND b) OR c

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

Логическая распределимость

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

e AND (f OR g) = (e AND f) OR (e AND g) и e OR (f AND g) = (e OR f) AND (e OR g)

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

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

Законы

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

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

Вот они:

НЕ (p И k) = НЕ (p) ИЛИ НЕ (k) и НЕ (p OR k) = НЕ (p) И НЕ (k)

Логический закон абсорбции

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

s AND (s OR w) = s и s OR (s AND w) = s

Помнить законы

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

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

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

Например …

Сводка

Коммутативность
a OR b = b OR
Личность
a OR False = a, h AND True = h
Дополнение
а ИЛИ НЕ (а) = Истина, а И НЕ (а) = Ложь
Идемпотент
a OR a = a, a AND a = a
Двойное отрицание
НЕ (НЕ (а)) =
Ассоциативность
a OR b OR c = (a OR b) OR c = a OR (b OR c)
a AND b AND c = (a AND b) AND c = a AND (b AND c)
Распределение
a AND (b OR c) = (a AND b) или (a AND c), a OR (b AND c) = (a OR b) AND (a OR c)
de Morgans ‘
НЕ (a И b) = НЕ (a) ИЛИ НЕ (b), НЕ (a ИЛИ b) = НЕ (a) И НЕ (b)
Абсорбционный
a AND (a OR b) = a, a OR (a AND b) = a
Двойственность
Обратите внимание на закономерности и отражения И и ИЛИ в правилах, и это поможет вам их легче запомнить.

Не могли бы вы просто положить нам Таблицы истинности?

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

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

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

Логические элементы алгебры и логики

Что такое булева алгебра?

В 1854 г., Джордж Буль, и 19 век Английский математик изобрел булеву / логическую / двоичную алгебру, с помощью которой рассуждения можно выразить математически.

Булева алгебра — одна из ветвей алгебры, которая выполняет операции с использованием переменных, которые могут принимать значения двоичных чисел, например, 0 (ВЫКЛ / Ложь) или 1 (ВКЛ / Истина) для анализа, упрощения и представления логические уровни цифровых / логических схем.

0 <1 , т.е. логический символ 1 больше, чем логический символ 0 .

Формула булевой алгебры

Ниже приведены операции булевой алгебры:

  1. ИЛИ Работа
  2. И Работа
  3. Не работает
ИЛИ Операция

Символ « + » обозначает оператор OR .

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

Операция OR определена для A OR B или A + B , как если бы A = B = 0 , тогда A + B = 0 или иначе A + B = 1.

Результат операции ИЛИ равен входной переменной с наибольшим значением.

Ниже приведены возможные выходы с минимум 2 комбинациями входов:

  • 0 + 0 = 0
  • 0 + 1 = 1
  • 1 + 0 = 1
  • 1 + 1 = 1
И Операция

Символ «. ’обозначает оператор И .

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

И операция определена для A AND B или A.B , если A = B = 1 , то A.B = 1 или еще A.B = 0.

Результат операции И равен входной переменной с наименьшим значением.

Ниже приведены возможные выходы с минимум 2 комбинациями входов:

  • 0 .0 = 0
  • 0 .1 = 0
  • 1 .0 = 0
  • 1 .1 = 1
Не работает Операция

Not также известна как операция дополнения . Это специальная операция, которая обозначается «» ». Дополнение к A представлено как A ’.

Для выполнения этой операции нам понадобится как минимум 1 входная переменная, которая может принимать значения двоичных чисел i.е., 0 или 1, чтобы получить на выходе одно двоичное значение (0/1).

Не операция определена для A ’ или НЕ A , если A = 1 , тогда A’ = 0 или в противном случае A ’= 1 .

Результатом операции not является значение, обратное заданному набору входных данных.

Ниже приведены возможные выходы с минимальным 1 входным значением:

Правила логической алгебры

Ниже приведены важные правила булевой алгебры.

  • Входные переменные, используемые в булевой алгебре, могут принимать значения двоичных чисел, например, 0 или 1 . Двоичное число 1 равно для HIGH , а двоичное 0 соответствует LOW .
  • Дополнение / отрицание / инверсия переменной представлено как
    Таким образом, дополнение переменной A представлено как A’ . Таким образом, A ’, если A = 1 , то A’ = 0 или еще A ’= 1
  • OR -Информация переменных представлена ​​знаком« + »между ними.Например, OR -ing из A , B представляется как A + B .
  • Логическое значение И двух или более переменных представлено как «. Знак ’между ними, например A.B . Когда-то «. ’можно опустить, как AB .

Логические законы
  1. Коммутативный закон
  2. Ассоциативный закон
  3. Распределительный закон
  4. И закон
  5. ИЛИ закон
Коммутативный закон

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

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

Ассоциативный закон

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

  • (A.B) .C = A. (B.C)
  • (A + B) + C = A + (B + C)
Распределительное право

Закон о распределении устанавливает следующие условия

  1. А.(B + C) = A.B + A.C
  2. A + (B.C) = (A + B). (A + C)
И закон

Закон «И» устанавливает следующие условия при использовании операций «И».

A.0 = 0
A.1 = A
A.A = A
A.A ’= 0

ИЛИ закон

Законы ИЛИ устанавливают следующие условия при использовании Операций ИЛИ.

A + 0 = A
A + A = A
A + 1 = 1
A + A ’= A

Закон о дополнении

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

  • (A ’)’ = A или A + (A ’)’ = 1

Таблица истинности булевой алгебры
Таблица истинности операций И ​​и операции ИЛИ
Таблица истинности операции И и операции ИЛИ
Таблица истинности операции НЕ Таблица истинности операции НЕ

Логические ворота

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

Типы логических вентилей
  1. AND Gate
  2. OR Gate
  3. NOT Gate
  4. NAND Gate
  5. NOR Gate
  6. XOR Gate
  7. Gate
  8. И выход

    Этот логический вентиль использует логику операции И и обозначается

    9165 9165 9165 9165 9165 9165
    Вход (A) Вход (B) Выход
    0 0 0
    0 1 1 0 0
    1 1 1
    Таблица истинности из AND Gate

    OR Выход

    Этот логический вентиль использует логику операции ИЛИ и обозначается

    Таблица истинности из OR Gate

    НЕ Ворота

    Этот логический вентиль использует логику операции НЕ и обозначен номером

    Он также известен как инвертор.

    NAND Gate

    Операция НЕ-И известна как операция И-НЕ, а логический вентиль, использующий эту логику операции И-НЕ, называется вентилем И-НЕ.

    Здесь выход логического элемента И является входом логического элемента НЕ, а выход этой комбинации элемента НЕ и И элемента является выходом элемента И НЕ .

    NAND Gate Схема

    NOR Gate

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

    Здесь выход элемента OR является входом элемента NOT , а выход этой комбинации элементов NOT и OR Элемент является выходом элемента NOR .

    Схема ворот NOR

    Вход ( A ) Вход (B) Выход ( A ⊕ B )
    0 0 0 0 90 1 0
    1 0 0
    1 1 0

    Ворота XOR

    XOR или EXOR или Exclusive-OR — это особый тип логического элемента или схемы, который даст высокий выход, если четное или нулевое количество входов будет высоким, иначе он даст низкий выход.

    Алгебраические выражения и оба представляют логический элемент XOR со входами A и B .

    Работа этих ворот обозначается

    Шлюз XOR Логика

    D = A XOR B
    D = A ⊕ B
    D = A’.B + A.B ’

    XOR Логическая схема
    Таблица истинности XOR
    Вход ( A ) Вход (B) Выход ( A ⊕ B )
    0
    0 0 0 90 1 1
    1 0 1
    1 1 0

    Ворота XNOR

    XNOR или EX-NOR или Исключительный вентиль NOR — это особый тип логического элемента или схемы, которая даст высокий выход, если нечетное количество входов будет высоким, иначе он даст низкий выход.Это противоположно вентилю XOR.

    Работа этих ворот обозначается « Ɵ» .

    Шлюз XNOR Логика

    D = A Ɵ B
    D = A’.B ’+ A.B

    Схема ворот XNOR
    XNOR Truth Таблица
    Вход ( A ) Вход (B) Выход ( A Ɵ B )
    0 0 0 0 0 90 1 0
    1 0 0
    1 1 1
    пожаловаться на это объявление

    Булева алгебра — все законы, правила, свойства и операции

    Булева алгебра — это ветвь алгебры, в которой переменные обозначаются логическими значениями. Истина (также обозначается 1) и Ложь (также обозначается 0). Вот и все. Это единственные два значения, с которыми мы будем иметь дело в булевой алгебре или цифровой электронике, если на то пошло. Булева алгебра отличается от математической алгебраической системы операциями, выполняемыми над ее переменными. Поскольку это новая система, к ней применяются некоторые новые правила и законы. Давай проверим это.

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

    Однажды утром вы просыпаетесь, и солнечный свет падает вам на лицо. Вы сонно подходите к кофеварке. Что это вы видите? 0 и 1 на машине? Что случилось с твоей кофеваркой? Вы открываете рот, чтобы выразить удивление. Но все, что вы можете сказать, это «да». И нет’. Вот и все. Ваши голосовые связки не поддерживают других слов.

    Вы трет глаза и осматриваетесь по комнате. Все в комнате — от пульта телевизора до мотивационных плакатов — на всем написано всего два слова.Какого черта!

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

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

    Назад в мир более двух цифр.

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

    Операция И обозначается Λ , операция ИЛИ обозначается , а ¬ обозначает операцию НЕ.В качестве альтернативы, a ( × ), ( + ) и (¯) обозначают операции AND, OR и NOT соответственно.

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

    История булевой алгебры

    Логическая система Аристотеля обрела новое лицо с использованием символических форм, введенных английским математиком Джорджем Булем.Буль ввел несколько соотношений между математическими величинами, которые имели только два значения: True или False, которые также можно было обозначать 1 или 0 соответственно. Позднее эта система была разработана как булева алгебра. Результаты всех математических операций, выполняемых с этими значениями, также могут иметь только два значения: 1 или 0.

    Зачем нам нужна логическая алгебра для сокращения логических выражений?

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

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

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

    В итоге

    Булева алгебра используется для упрощения сложных логических выражений цифровой схемы. Тем самым позволяя нам сокращать сложные схемы до более простых. Это выглядит примерно так. Сложная схема -> Найти уравнение -> Уменьшить с помощью логических законов -> Изменить схему на основе нового более простого уравнения.

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

    Операция НЕ и ее правила

    Логическое НЕ (!) Выполняет функцию инверсии.Операция НЕ называется так, потому что вывод НЕ совпадает с вводом.

    Применение операции NOT к переменной «Истина» приводит к выводу «Ложь». Точно так же применение операции NOT к переменной «False» приводит к выводу True. Его можно сравнить с простым вентилем НЕ, который инвертирует / дополняет вход логической «1» до логического «0» и наоборот.

    Закон о дополнении

    Когда между переменной и ее дополнением выполняется операция ИЛИ, результат равен 1.Точно так же, когда операция И выполняется между переменной и ее дополнением, результат равен 0.

    A + A ‘= 1
    A A’ РЕЗУЛЬТАТ
    0 1 1
    1 0 1
    9. A ‘= 0
    A A’ РЕЗУЛЬТАТ
    0 1 0 1 0

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

    Закон в основном гласит, что если вы дважды примените операцию NOT к переменной, вы вернетесь к исходной переменной без какого-либо изменения ее значения.Рассмотрим переменную A. Пусть отрицание A, то есть A ‘задается Y. Если мы выполним операцию отрицания над Y, мы вернем переменную A.

    (A’) ‘= A
    A A ‘= Y (A’) ‘
    0 1 0 1


    Операция AND и ее правила

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

    Операция AND следует нескольким правилам / свойствам / законам в отношении своей функциональности, а именно закону аннулирования, свойству Identity, свойству Idempotent, свойству Complement и свойству Commutative. Давайте рассмотрим A как логическую переменную, имеющую значение 0 или 1.

    Закон об аннулировании

    A. 0 = 0

    Identity Property

    A. 1 = A

    Идемпотентное свойство

    A.A = A

    Дополнительное имущество

    A. A ’= 0

    Операция ИЛИ и ее правила

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

    Как и операция И, операция ИЛИ подчиняется некоторым законам в отношении своей функциональности. А именно: Закон об аннулировании, свойство Identity, свойство Idempotent, свойство Complement и свойство Commutative.Рассмотрим A как логическую переменную, имеющую значение 0 или 1.

    Закон об аннулировании

    A + 1 = 1

    Свойство идентичности

    A + 0 = A

    Идемпотентный Свойство

    A + A = A

    Свойство дополнения

    A + A ‘= 1

    Распределительные законы булевой алгебры

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

    9067 Заявление 1

    Рассмотрим три переменные A, B и C.Когда две переменные соединяются оператором И и ИЛИ с третьей переменной, результат совпадает с операцией ИЛИ первой и второй переменной с третьей по отдельности, а затем складывается И их результат.

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

    А + (В. С) = (А + В). (A + C)

    Здесь OR распределяет по операции AND.

    ДОКАЗАТЕЛЬСТВО

    A + (BC) = (A. 1) + (BC) [A.1 = A по свойству идентичности AND]

    = (A. (1 + B)) + (BC ) [1 + B = 1 по свойству аннулирования OR]

    = (A.1) + (AB) + (BC)

    = (A. (1 + C)) + (AB) + (BC)

    = A. (A + C) + B. (A + C) [AA = A.1 = A]

    = (A + C). (A + B)

    Следовательно, закон распределения Справедливо.

    Заявление 2

    Рассмотрим три переменные A, B и C. Когда две переменные объединяются по ИЛИ и И с третьей переменной, результат такой же, как И для первой и второй переменной с третьей переменной отдельно, а затем ИЛИ их результат.

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

    А.(B + C) = (A.B) + (A.C)

    Здесь AND распределяет по операции OR.

    ДОКАЗАТЕЛЬСТВО

    A. (B + C) = A. (B.1) + A. (C.1) [1.B = B, 1.C = C по свойству идентичности AND]

    = [(A.B). (A.1)] + [(A.C). (A.1)]

    = [(A.B). A] + [(A.C) .A]

    = (A +1). [(A.B) + (A.C)]

    = (A.B + A.C) [1 + A = 1 по свойству аннулирования OR]

    Следовательно, закон распределения выполняется.

    Коммутативные законы булевой алгебры

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

    A + B = B + A

    A. В = В. A

    Ассоциативные законы булевой алгебры

    В соответствии с ассоциативными законами есть два утверждения:

    Ассоциативный закон с использованием функции ИЛИ

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

    P + (Q + R) = (P + Q) + R

    Ассоциативный закон с использованием функции AND

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

    с. (Q. R) = (P. Q). R

    Свойство поглощения

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

    ИЛИ Закон поглощения

    A + (A. B) = A

    ДОКАЗАТЕЛЬСТВО

    A + (A. B) = (A. 1) + (A. B) [A.1 = A по свойству идентичности AND]

    = A (1 + B)

    = A.1 [1 + B = 1 по свойству аннулирования OR]

    = A

    AND Закон поглощения

    А.(A + B) = A

    ДОКАЗАТЕЛЬСТВО

    A. (A + B) = (A. A) + (A. B) [Распределительное свойство]

    = A + (A. B) [AA = A по идемпотентному свойству AND]

    = A (1 + B)

    = A.1 [1 + B = 1 по свойству аннулирования OR]

    = A

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

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

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

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

    ОПЕРАТОР СИМВОЛ ПРЕДЫДУЩИЙ
    Наивысший
    И . Средний
    OR + Самый низкий

    Теорема Де Моргана

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

    Заявление 1

    «Отрицание дизъюнкции — это соединение отрицаний», т. Е. НЕ (А ИЛИ B) = НЕ А И НЕ Б. Его также можно сформулировать как:

    «Дополнение объединение двух множеств совпадает с пересечением их дополнений. ‘

    Заявление 2

    ‘ Отрицание конъюнкции — это дизъюнкция отрицаний ‘, т.е. НЕ (А И В) = НЕ А ИЛИ НЕ Б .Его также можно сформулировать как:

    «Дополнение пересечения двух множеств совпадает с объединением их дополнений».

    Принцип двойственности

    Двойственное логическое выражение может быть получено заменой всех Операторы И на ИЛИ и все операторы ИЛИ на И, а также путем замены всех двоичных значений, то есть всех 0 на 1 и всех 1 на 0 в уравнении.

    Основные шаги, которые необходимо выполнить, следуя принципу двойственности:

    • Заменить все операторы И на операторы ИЛИ
    • Заменить все операторы ИЛИ на операторы И
    • Дополнить все единицы до 0
    • Дополнить все нули к 1с
    ЗНАЧЕНИЕ ДВОЙНОЕ
    Оператор ИЛИ Оператор И
    Оператор И

    2

    2

    Оператор И 1
    A A ‘
    A’ A

    Теорема избыточности / консенсуса

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

    • Выражение должно содержать три переменные
    • Каждая переменная должна повторяться дважды, даже если она находится в ее дополненной форме
    • Только одна из трех переменных должна быть в дополненной форме
    • Для сокращения рассмотрим термины, содержащие переменную, которая была дополнена

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

    Вот пример теоремы о избыточности с ее доказательством.

    Пусть Y = AB + A’C + BC — данное уравнение. Посмотрим, соответствует ли он данным критериям теоремы консенсуса.

    • Данное уравнение Y имеет три переменные A, B и C.
    • Каждая переменная A, B и C повторяется дважды, даже если A дополняется.
    • Только одна переменная, то есть A дополняется в уравнении
    • Рассмотрим члены, в которых присутствует A, поскольку A является дополненным членом.

    Таким образом, сокращенное уравнение имеет вид Y = AB + A’C. г. до н.э. — это консенсус терминов AB и A’C.

    Теперь проверим доказательство.

    Y = (A. B) + (A ‘. C) + (B. C)

    = (A. B) + (A’. C) + (B. C. 1)

    = (A .B) + (A ‘. C) + (B. C. (A + A’)) [A + A ‘= 1 по свойству дополнения OR]

    = (A. B) + (A’. C) + (A .B. C) + (A ‘. B. C)

    = (A. B) (1 + C) + (A’. C) (1 + B) [1 + B = 1 + C = 1 по праву аннулирования OR]

    Y = (A.B) + (A ’. C)

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

    • F = (А + В). (A ’+ C). (B + C)
    1. Данное уравнение F имеет три переменные A, B и C.
    2. Каждая переменная A, B и C повторяется дважды, даже если A дополняется.
    3. Только одна переменная, то есть A дополняется в уравнении
    4. Рассмотрим члены, в которых присутствует A, поскольку A является дополненным членом.

    Таким образом, F = (A + B). (A ‘+ C)

    • G = (P. Q’) + (P. R) + (Q. R)
    1. Данное уравнение G имеет три переменные P, Q и R.
    2. Каждая переменные P, Q и R повторяются дважды, даже если Q дополняется.
    3. Только одна переменная, то есть Q дополняется в уравнении
    4. Рассмотрим члены, в которых присутствует A, поскольку A является дополняемым членом.

    Таким образом, G = (P. Q ’) + (Q. R)

    • Y = (D’ + F).(E ’+ F’). (D ’+ E’)
    1. Данное уравнение Y имеет три переменные D ’, E’ и F ’.
    2. Каждая переменная D ’, E’ и F ’повторяется дважды, даже если F’ дополняется.
    3. Только одна переменная, то есть F ’, дополняется в уравнении
    4. Рассмотрим члены, в которых присутствует F’, поскольку F ’является дополненным членом.

    Таким образом, Y = (D ’+ F). (E ’+ F’)

    • Z = (A. B) + (B. C ’) + (A. C)
    1. Данное уравнение Z имеет три переменные A, B и C.
    2. Каждая переменная A, B и C повторяется дважды, даже если C дополняется.
    3. Только одна переменная, то есть C, дополняется в уравнении
    4. Рассмотрим члены, в которых присутствует C, поскольку C является дополняемым членом.

    Таким образом, Z = (B. C ’) + (A. C)

    Интересно? Попробуйте сами и дайте ответы в комментариях! Объясните также причину своего ответа!

    N = (P + R). (Q + R ’). (P + Q)

    Преобразование логических схем в эквиваленты булевых выражений — пример

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

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

    Шаг 1

    Шаг 2

    Шаг 3

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

    Выход схемы был (A.B) + (B. C). (B + C) , но мы могли бы еще больше упростить его до B. (А + С). Следовательно, B. (A + C) является последним эквивалентом логического выражения данной логической схемы.

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

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

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

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

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

    Вот и все! Вот и ваша последняя схема!

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

    Надеюсь, теперь у вас есть элементарное представление о том, чего нам может достичь булева алгебра.

alexxlab

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *