1 Булевы функции, стрелка Пирса и штрих Шеффера on Vimeo

Минимизация логических функций двух переменных

1.Конъюнкция

                    X1 X2

2.Запрет по Х1

                          ØX1 X2

3.Повторение X1

                                            X1

4.Запрет по Х2

                                        X1 ØX2     

5.Повторение X2

                                              X2

6.Сложение по модулю 2

 

ØX1X2 или ØX2 X1

7.Дизъюнкция

                                      X1 или X2 

8.Стрелка Пирса

ØX1ØX2

Представление логических функций через базовые функции

Функции И, ИЛИ, НЕ не являются единственным набором базовых функции. Существую ещё несколько наборов базовых функций, представляющих все другие функции.

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

Теорема 2

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

Доказательство

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

Видео

Стрелка Пирса

Бинарная логическая операция, булева функция над двумя переменными. Названа в честь Чарльза Пирса и введена в алгебру логики в $1880—1881$ гг.

Обозначения: $\downarrow$ , ИЛИ-НЕ

Таблица истинности для стрелки Пирса


Рисунок 7.

Свойства:

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

$X \downarrow X = ¬X$— отрицание

$(X \downarrow Y) \downarrow (X \downarrow Y) \equiv X \vee Y$ — дизъюнкция

$(X \downarrow X) \downarrow (Y \downarrow Y) \equiv X \wedge Y$ — конъюнкция

$((X \downarrow X) \downarrow Y) \downarrow ((X \downarrow X) \downarrow Y) = X \to Y$ — импликация

В электронике стрелка Пирса представлена в виде элемента, который носит название «операция 2ИЛИ-НЕ» (2-in NОR).

Отрицание, логическое отрицание или инверсия (в теории множеств это отрицание)

Отрицание — означает, что к исходному логическому выражению добавляется частица НЕ или слова НЕВЕРНО, ЧТО и в итоге получаем, что если исходное выражение истинно, то отрицание исходного – будет ложно и наоборот, если исходное выражение ложно, то его отрицание будет истинно.

Обозначения: не $A$, $\bar{A}$, $¬A$.

Таблица истинности для инверсии


Рисунок 3.

Свойства отрицания:

«Двойное отрицание» $¬¬A$ является следствием суждения $A$, то есть имеет место тавтология в формальной логике и равно самому значению в булевой логике.

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

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

Обозначается дизъюнкция союзом «или», символами +,\( \vee\).

Таблица истинности логического сложения:

A, B — входная информация;

A или B — значение, приобретаемое в результате выполнения дизъюнкции.

Для дизъюнкции справедливы следующие утверждения:

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

Представление логических функций через импликацию

Теорема 5

Через функцию  импликация Y = X1®X2 = Ø X1ÚX2 можно представить любую другую логическую функцию.

Доказательство

Согласно теореме 2 для того, чтобы функция импликации была базовой достаточно представить через неё функции И, ИЛИ, НЕ.

Отрицание ØХ1 =ØХ1Ú1 = Х1®1

Конъюнкция    Х1Ù Х2 = Ø(ØХ1ÚØХ2) = Ø (X1®ØX2)=(X1®ØX2) ®1

=( X1®(X2®1) ®1

Дизъюнкция Х1ÚХ2 = Ø(ØХ1)ÚХ2 = (ØХ1) ®Х2 = (Х1®1)®Х2

Теорема доказана.

Литература:

1.А.А. Ивин Логика, учебное пособие издание 2 Москва,  Знание 1998

2.Д.А. Владимиров Булевы алгебры Москва, Наука 1969

3.Википедия свободная энциклопедия, Логика http:///

4.Н.Н. Моисеева Методические разработки, учебный сайт http:///sch1019/

 

Теги

Adblock
detector