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

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

Алгебра логики - раздел математики. Она  оперирует логическими высказываниями.

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

"Москва - столица России" (высказывание  истинно).

"После зимы наступает осень" (высказывание ложно).

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

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

"Иван сдает экзамен по  физике и информатике".

Высказывание содержит два утвеждения, объединенных "и":

Утверждение1: "Иван сдает экзамен  по физике".

Утверждение2: "Иван сдает экзамен  по информатике".

"Игорь решил записаться в  секцию по воллейболу или баскетболу".

Высказывание содержит два утвеждения, объединенных "или":

Утверждение1: "Игорь решил записаться в секцию по воллейболу".

Утверждение2: "Игорь решил записаться в секцию по баскетболу".

"Если Илья будет много  готовиться самостоятельно и  будет заниматься с репетитором,  то он поступит в ВУЗ".

Высказывание содержит три утвеждения, объединенных связкой "если, то" и союзом "и":

Утверждение1: "Илья будет много  готовиться самостоятельно".

Утверждение2: "Илья будет заниматься с репетитором".

Утверждение2: "Илья поступит в ВУЗ".

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

Логическое выражение - простое  или сложное логическое высказывание, представленное в формальном виде. Примеры логических выражений:

простое: A,

сложное: AVB→C,\

где A, B, C - утверждения;

Λ, V, → - логические операции.

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

Логическая переменная - переменная, которая может принимать значение 1 (истина) или 0 (ложь).

Логическая функция - функция, аргументы  и значение которой могут принимать  значение 1 (истина) или 0 (ложь).

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

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

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

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

· f10 –  инверсия (логическая связь  НЕ, логическое отрицание);

· f1 – конъюнкция (логическая связь  И, логическое умножение),

· f7 –  дизъюнкция (логическая связь  ИЛИ, логическое сложение).

Этот набор получил название функционально полной системы логических функций (ОФПС). Из теоремы о функциональной полноте следует, что основная функционально  полная система логических функций  является избыточной, так как условиям теоремы отвечают наборы функций f10 и f1 или f10 и f7.  Свойства этих функций  были рассмотрены ранее.

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

2. Законы алгебры логики в  ОФПС и их следствия. В алгебре  логики имеются четыре основных  закона, регламентирующих порядок  производства операций НЕ, И, ИЛИ  в любом логическом выражении:

· переместительный (коммутативный);

· сочетательный (ассоциативный);

· распределительный (дистрибутивный);

· инверсии (правило Де Моргана).

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

x1 Úx2 = x2 Úx1;               x1 Ùx2 = x2 Ù x1.                                         (1)

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

Сочетательный закон. Этот закон, так  же как и переместительный, является симметричным, т. е. справедливым и для  дизъюнкции, и для конъюнкции:

x1 Úx2 Úx3 = x1Ú(x2 Úx3) = (x1 Úx2)Úx3= x2Ú( x1 Úx3);            (2)

x1 Ùx2 Ùx3 = x1Ùx2 Ùx3) = (x1 Ùx2)Ùx3= x2Ù( x1 Ùx3).

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

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

для логического умножения относительно логического сложения (распределительный  закон 1-го рода) и для логического  сложения относительно логического  умножения (распределительный закон 2-го рода).

1. Распределительный закон 1-го  рода записывается следующим  образом:

(x1Úx2)Ùx3=(x1Ùx3)Ú ( x2 Ùx3) .                                        (3)

Справедливость формулы (5.3), а также  и ее более общего случая, когда  в скобках заключена сумма  любого количества слагаемых, можно  доказать путем установления идентичности условий обращения в 0 или 1 ее левой  и правой частей. Условием обращения в нуль левой части выражения (5.3) состоит в том, чтобы нулю равнялся либо один аргумент х3, либо одновременно аргументы x1 и x2. Условия обращения в нуль правой части выражения (5.1)  такие же. Следовательно, распределительный закон 1-го рода справедлив для алгебры логики.

2. Распределительный закон 2-го  рода имеет вид

(x1Ùx2)Úx3=(x1Úx3)Ù ( x2Úx3).                               (4)

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

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

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

                             (5)

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

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

                            (6)

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

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

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

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

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

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

Правило склеивания. Прежде чем сформулировать само правило, введем некоторые новые  понятия. Если имеется некоторый  конечный набор логических аргументов x1, x2, … xn, то логическое произведение любого их числа называется элементарным в том случае, когда сомножителями в нем являются либо одиночные аргументы, либо отрицания одиночных аргументов. Так, например, f1(х1, х2, x3, х4)= х1× х2× x3×х4 — элементарное произведение (элементарная конъюнкция); —не является элементарным произведением.

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

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

f1(х1, х2, x3, х4)= х1× х2× x3×х4 и f3(х1, х2, x3, х4)=

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

f3(х1, х2, x3, х4)=  и f4(х1, х2, x3, х4)=

соседними не являются.

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

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

Например,

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

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

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

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

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

Например:

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

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

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

Это правило является следствием распределительного закона 2-го рода и также находит  широкое применение для упрощения  логических функций.

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

· в развертываемую элементарную конъюнкцию ранга r в качестве дополнительных сомножителей вводится п-r единиц, где п — ранг конституенты;

· каждая единица представляется в  виде логической суммы некоторой, не имеющейся в исходной конъюнкции переменной и ее отрицания: ;

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

Пример  Развернуть элементарную конъюнкцию f(x1,x2,x3,x4) = =x1×x3  в логическую сумму конституент единицы.

Решение. Ранг конституенты единицы для данной функции равен 4. Производим развертывание исходной конъюнкции поэтапно в соответствии с правилом развертывания:

1-й этап— f(x1,x2,x3,x4) = x1×1×x3×1.

2-й этап — f(x1,x2,x3,x4) =

3-й этап — f(x1,x2,x3,x4)=

= что и требовалось получить.

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

· в развертываемую элементарную дизъюнкцию ранга r в качестве дополнительных слагаемых вводится п-r нулей;

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

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

Пример.  Развернуть элементарную дизъюнкцию f(x1,x2,x3,x4)= =x3Úx4  в логическое произведение конституент нуля.

Решение. Ранг конституенты нуля п = 4. Далее производим развертывание исходной дизъюнкции поэтапно в соответствии с правилом развертывания:

1-й этап — f(x1,x2,x3,x4) =0Ú0Úx3Úx4;

2-й этап — f(x1,x2,x3,x4) =

3-йэтап—f(x1,x2,x3,x4)=

что и требовалось получить.

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

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

Операция Пирса (стрелка Пирса) реализует функцию, которая принимает  значение, равное единице только в  том случае, когда все ее аргументы  равны 0 (ИЛИ-НЕ), что может быть записано в ОФПС для функции двух переменных следующим образом:

         (7)

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

        (8)

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

·   представить переключательную функцию f в конъюнктивной нормальной форме;

·   полученное выражение представить  в виде (поставить два знака  отрицания);

·   применить правило Де Моргана.

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

в базисе Пирса, необходимо выполнить  следующие преобразования:

Для представления полученного  выражения в базисе Пирса воспользуемся  соотношением (7):

Операция Шеффера (штрих Шеффера) реализует функцию, которая принимает  значение, равное нулю, только в том  случае,   когда все ее аргументы  равны 1 (И-НЕ), что может быть записано в ОФПС для функции двух переменных следующим образом:

                      (9)

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

f(x1,x2,…,xn)= x1½x2½…½xn =          (10)

Для представления переключательной функции в базисе Шеффера необходимо выполнить следующие действия:

·   представить переключательную функцию f в дизъюнктивной нормальной форме;

·   полученное выражение представить  в виде (поставить два знака  отрицания);

·   применить правило Де Моргана.

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

в базисе Шеффера, необходимо выполнить  следующие преобразования:

Для представления полученного  выражения в базисе Шеффера воспользуемся  соотношением (5.9):

f(x1,x2,x3,x4)=(x4½x2)½(x3½x1).

Индукционные  приборы.

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

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

Приведенная конструкция (трехпоточная) счетчика со стоит из двух электромагнитов и подвижного алюминиевого диска . Диск укреплен на оси, которая связана с помощью червячной передачи со счетным механизмом. Диск вращается в зазоре электромагнитов. Магнитный поток Ф1 электромагнита 1 U-образной формы создается током I приемника электрической энергии, так как его обмотка включена последовательно в цепь нагрузки. Поток Ф1 дважды пересекает диск и не значительно отстает по фазе от образующего его тока I. Поэтому можно считать, что значение потока Ф1 в первом приближении пропорционально току I: Ф1 = kI. Электромагнит 2 имеет Т-образный вид. На его среднем стержне расположена гистерезис и вихревые токи.

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

Так как реактивное сопротивление  этой обмотки большое, можно считать, что ее полное сопротивление ZU »  ХU, и ток IU в обмотке сдвинут  по фазе относительно напряжения U почти  на p/2. Поток ФU, как видно из рисунка, делится на две части: рабочий поток Фр и потоки ФL, которые замыкаются по мимо диска по боковым ветвям магнито провода .

Та ким образом,

ФU = ФP + 2ФL.

Рабочий поток Фр проходит по среднему стержню магнито провода и пересекает диск, замыкаясь через противо полюсную скобу , средняя часть которой находится под центральным стержнем магнито провода . При такой конструкции под диском находятся три полюса (два от U-образного магнита и один от Т-образного магни та). Потоки ФL определяют сдвиг по фазе между потоками ФP и Фr Вихревые токи, индуцируемые в диске магнитными потоками, пропорциональны магнитным потокам и частоте. Магнитный поток ФP индуцирует в диске вихревой ток.

Взаимодействие между индуцируемым током в диске и созданным  им потоком, например, между IвI и Фr, не создает электромагнитной силы, так как g = p/2 и cosg = 0. Электромагнитные силы создаются только в результате взаимодействия магнитного потока ФP с током IвI и пото ка ФI с током Iв.р.

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

ЭДС Ев = -Фda/dt,

под действием которой в нем  возникает вихревой ток 

в = Ев/Rд,

где Rд - сопротивление диска. Когда моменты равны, т. е. Мт = Мвр, частота вращения диска постоянна (установившийся режим).

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

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

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

Индукционные счетчики весьма надежны в эксплуатации.

ЛИТЕРАТУРА

1. Белоусов А.И., Ткачев С.Б. Дискретная  математика: Учебник для ВУЗов  / Под ред. В.С. Зарубина, А.П.  Крищенко.– М.: изд-во МГТУ им. Н.Э. Баумана, 2001.– 744 с. (Сер. Математика в техническом университете; Вып XIX).

2. Горбатов В.А. Фундаментальные  основы дискретной математики. Информационная  математика.– М.: Наука, Физматлит, 2000.– 544 с.– ISBN 5-02-015238-2.

3. Петрова В.Т. Лекции по алгебре  и геометрии. Учебник для ВУЗов:  в 2 ч.– М.: Гуманит. изд. центр ВЛАДОС.– ч. 1 – 312 с., ч. 2 – 344 с. ISBN 5-691-00077-2. ISBN 5-691-00238-4 (I), ISBN 5-691-00239-2 (II).

4. Зарубин В.С. Математическое  моделирование в технике: Учеб. для ВУЗов / Под ред. В.С. Зарубина, А.П. Крищенко.– М.: Изд-во МГТУ им. Н.Э. Баумана, 2001.– 496 с. (Сер. Математика в техническом университете; вып. XXI, заключительный).

5. Кораблев В. П. Электробезопасность. - М.: Колос, 2001 -200 с.

6. Минин Г.П. Эксплуатация электроизмерительных приборов. - Москва, 2000 - 236 с.

7. Телешевский Б.Е. «Измерения в электро и радиотехнике», М «Высшая шкала», 2003 - 325 с.

8. Фремке А.В. и др. Электрические измерения. - М.: Энергия, 2003 - 269 с.