Форум программистов, компьютерный форум, киберфорум
Assembler, MASM, TASM
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.63/2256: Рейтинг темы: голосов - 2256, средняя оценка - 4.63
Ушел с форума
Автор FAQ
 Аватар для Mikl___
16383 / 7695 / 1080
Регистрация: 11.11.2010
Сообщений: 13,783
14.11.2013, 07:10  [ТС]
ГЛАВА 8
БУЛЕВА АЛГЕБРА
(часть 1/2)

Характерная черта современных компьютеров — сведение всех вычислительных структур к двоичным числам и алгоритмам их обработки.
Алгебра логики
Алгебра логики — раздел математической логики, в котором изучаются логические операции над высказываниями. Высказывания могут быть истинными (true) и ложными (false).
Определение
Высказывания строятся над множеством {https://www.cyberforum.ru/cgi-bin/latex.cgi?\Re, ¬, https://www.cyberforum.ru/cgi-bin/latex.cgi?\vee, https://www.cyberforum.ru/cgi-bin/latex.cgi?\wedge, 0, 1}, где https://www.cyberforum.ru/cgi-bin/latex.cgi?\Re — непустое множество, над элементами которого определены три базовых операции:
  • ¬ одноместная (унарная) операция отрицание («логическое НЕ»). Для обозначения операции НЕ в алгебре логики так же может использоваться черта над символом; «НЕ https://www.cyberforum.ru/cgi-bin/latex.cgi?A» записывается как https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{A} ;
  • https://www.cyberforum.ru/cgi-bin/latex.cgi?\wedge — двуместная (бинарная) операция конъюнкция («логическое И»). Конъюкция нескольких предложений истина, только если все они истины. Кроме знака https://www.cyberforum.ru/cgi-bin/latex.cgi?\wedge для обозначения операции «логическое И» иногда используется точка (·) или слитное написание операторов; операция «https://www.cyberforum.ru/cgi-bin/latex.cgi?A и https://www.cyberforum.ru/cgi-bin/latex.cgi?B» записывается как https://www.cyberforum.ru/cgi-bin/latex.cgi?A\cdot B, или просто https://www.cyberforum.ru/cgi-bin/latex.cgi?AB;
  • https://www.cyberforum.ru/cgi-bin/latex.cgi?\vee — двуместная операция дизъюнкция («логическое включающее ИЛИ»). Дизъюнкция нескольких предложений ложна в точности тогда, когда все они ложны. Кроме знака https://www.cyberforum.ru/cgi-bin/latex.cgi?\vee для обозначения операции «логическое включающее ИЛИ» иногда используется +; операция «https://www.cyberforum.ru/cgi-bin/latex.cgi?A или https://www.cyberforum.ru/cgi-bin/latex.cgi?B» записывается как https://www.cyberforum.ru/cgi-bin/latex.cgi?A+B;
  • а также две константы — логический ноль 0 (false) и логическая единица 1 (true).
Операции над булевскими значениями (логическая конъюкция, дизъюнкция и отрицание) приведены в таблице 8.1.
Булевские операции
Булевы или логические выражения состоят из булевской операции и одного или нескольких операндов. Операнды логических выражений также могут являться логическими выражениями.
https://www.cyberforum.ru/cgi-bin/latex.cgi?Ahttps://www.cyberforum.ru/cgi-bin/latex.cgi?Bhttps://www.cyberforum.ru/cgi-bin/latex.cgi?A\vee Bhttps://www.cyberforum.ru/cgi-bin/latex.cgi?A\wedge Bhttps://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{A}
1 1 1 1 0
1 0 1 0 0
0 1 1 0 1
0 0 0 0 1
Таблица 8.1.
Дизъюнкт — пропозициональная формула, являющаяся дизъюнкцией двух или более литералов (например, https://www.cyberforum.ru/cgi-bin/latex.cgi?A \vee \bar{B} \vee C ). Конъюнкт — пропозициональная формула, являющаяся конъюнкцией двух или более литералов (например, https://www.cyberforum.ru/cgi-bin/latex.cgi?A \wedge \bar{B} \wedge C ). Для обозначения эквивалентности логических выражений используется знак равенства «=».
Примеры булевых выражений
ВыражениеОписание
https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{A}Не https://www.cyberforum.ru/cgi-bin/latex.cgi?A
https://www.cyberforum.ru/cgi-bin/latex.cgi?A\cdot Bhttps://www.cyberforum.ru/cgi-bin/latex.cgi?A и https://www.cyberforum.ru/cgi-bin/latex.cgi?B
https://www.cyberforum.ru/cgi-bin/latex.cgi?A+Bhttps://www.cyberforum.ru/cgi-bin/latex.cgi?A или https://www.cyberforum.ru/cgi-bin/latex.cgi?B
https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{A}+BНе https://www.cyberforum.ru/cgi-bin/latex.cgi?A или https://www.cyberforum.ru/cgi-bin/latex.cgi?B
https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{AB}Не (https://www.cyberforum.ru/cgi-bin/latex.cgi?A и https://www.cyberforum.ru/cgi-bin/latex.cgi?B)
https://www.cyberforum.ru/cgi-bin/latex.cgi?A\bar{B}https://www.cyberforum.ru/cgi-bin/latex.cgi?A и не https://www.cyberforum.ru/cgi-bin/latex.cgi?B

Порядок выполнения операторов
операцияприоритет
¬1
https://www.cyberforum.ru/cgi-bin/latex.cgi?\wedge2
https://www.cyberforum.ru/cgi-bin/latex.cgi?\vee3
https://www.cyberforum.ru/cgi-bin/latex.cgi?\rightarrow4
В сложных выражениях, состоящих из нескольких логических операторов важен порядок их выполнения. Операция «НЕ» имеет наивысший приоритет, то есть выполняется всегда первой. После отрицания выполняется операция логического «И», предпоследней выполняется логическое «ИЛИ». Чтобы избежать ошибок при анализе логических выражений используют скобки.
Порядок выполнения логических операторов
Выражение Порядок выполнения
https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{A}+BНе, затем ИЛИ
https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{A+B}ИЛИ, затем НЕ
https://www.cyberforum.ru/cgi-bin/latex.cgi?A+B\cdot CИ, затем ИЛИ

Логические операции
Простейшим и наиболее широко применяемым примером такой алгебраической системы является множество https://www.cyberforum.ru/cgi-bin/latex.cgi?\Re состоящее всего из двух элементов:
https://www.cyberforum.ru/cgi-bin/latex.cgi?\Re = {Ложь, Истина}
Как правило, в математических выражениях Ложь отождествляется с логическим нулём, а Истина — с логической единицей, а операции отрицания (НЕ), конъюнкции (И) и дизъюнкции (ИЛИ) определяются в привычном нам понимании. В общем случае логические выражения являются функциями логических переменных https://www.cyberforum.ru/cgi-bin/latex.cgi?A,https://www.cyberforum.ru/cgi-bin/latex.cgi?B,https://www.cyberforum.ru/cgi-bin/latex.cgi?C, каждая из которых может иметь значения 0 или 1. Для каждого набора переменных логическая функция https://www.cyberforum.ru/cgi-bin/latex.cgi?F может принимать значение 0 или 1. Любую логическую функцию можно задать в виде таблицы, в которой указаны все возможные наборы значений аргументов и соответствующие значения функций. Если имеется https://www.cyberforum.ru/cgi-bin/latex.cgi?n логических переменных, то они образуют https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{n} возможных логических наборов из 0 и 1.
При https://www.cyberforum.ru/cgi-bin/latex.cgi?n=1: https://www.cyberforum.ru/cgi-bin/latex.cgi?A=0 и https://www.cyberforum.ru/cgi-bin/latex.cgi?A=1 таблица функции от одного аргумента будет выглядеть так:
AF1F2F3F4
00011
10101
Таблица 8.2
функция https://www.cyberforum.ru/cgi-bin/latex.cgi?F_{1} принимает значение 0 при любых значениях аргумента, то есть это константа 0, аналогично https://www.cyberforum.ru/cgi-bin/latex.cgi?F_{4} — константа 1. Значения этих функций не зависят от https://www.cyberforum.ru/cgi-bin/latex.cgi?A поэтому говорят, что для них переменная https://www.cyberforum.ru/cgi-bin/latex.cgi?A несущественна. Функция https://www.cyberforum.ru/cgi-bin/latex.cgi?F_{3} заменяет значение своего аргумента на противоположное и называется отрицанием. Функция https://www.cyberforum.ru/cgi-bin/latex.cgi?F_{2} называется повторением.
Логических функций одной переменной насчитывается всего четыре. В общем же случае число логических функций при https://www.cyberforum.ru/cgi-bin/latex.cgi?n переменных будет равно https://www.cyberforum.ru/cgi-bin/latex.cgi?\ell_{n}=2^{2^{n}}. (https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{n} - это число возможных наборов длины https://www.cyberforum.ru/cgi-bin/latex.cgi?n, состоящих из 0 и 1, то есть число строк таблицы. Тогда https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{2^{n}} равно количеству различных расстановок 0 и 1 в столбце с таким количеством строк.) Значит, логических функций двух переменных должно быть https://www.cyberforum.ru/cgi-bin/latex.cgi?\ell_{2}=2^{2^{2}}=2^{4}=16 далее при увеличении https://www.cyberforum.ru/cgi-bin/latex.cgi?n число https://www.cyberforum.ru/cgi-bin/latex.cgi?\ell_{n} растет чрезвычайно быстро: https://www.cyberforum.ru/cgi-bin/latex.cgi?\ell_{3}=2^{2^{3}}=2^{8}=256, https://www.cyberforum.ru/cgi-bin/latex.cgi?\ell_{4}=2^{2^{4}}=2^{16}=65536 и т.д.
Подробно рассмотрим логические функции от двух переменных.
ABF1 F2F3F4F5F6F7F8F9F10F11F12F13F14F15F16
000000000011111111
010000111100001111
100011001100110011
110101010101010101
Таблица 8.3
Как и в случае функции одной переменной, функции https://www.cyberforum.ru/cgi-bin/latex.cgi?F_{1} и https://www.cyberforum.ru/cgi-bin/latex.cgi?F_{16} — это константы, соответственно 0 и 1. Для них обе переменные несущественны. Для функций https://www.cyberforum.ru/cgi-bin/latex.cgi?F_{4} и https://www.cyberforum.ru/cgi-bin/latex.cgi?F_{13} не существенна переменная https://www.cyberforum.ru/cgi-bin/latex.cgi?B, поскольку https://www.cyberforum.ru/cgi-bin/latex.cgi?F_{4}=A, а https://www.cyberforum.ru/cgi-bin/latex.cgi?F_{13}=\bar{A}. А для функций https://www.cyberforum.ru/cgi-bin/latex.cgi?F_{6} и https://www.cyberforum.ru/cgi-bin/latex.cgi?F_{11} не существенна переменная https://www.cyberforum.ru/cgi-bin/latex.cgi?A, поскольку https://www.cyberforum.ru/cgi-bin/latex.cgi?F_{6}=B, а https://www.cyberforum.ru/cgi-bin/latex.cgi?F_{11}=\bar{B}. Функция https://www.cyberforum.ru/cgi-bin/latex.cgi?F_{2} уже знакомая Вам конъюкция https://www.cyberforum.ru/cgi-bin/latex.cgi?A и https://www.cyberforum.ru/cgi-bin/latex.cgi?B, функция https://www.cyberforum.ru/cgi-bin/latex.cgi?F_{8} так же знакомая Вам дизъюкция https://www.cyberforum.ru/cgi-bin/latex.cgi?A и https://www.cyberforum.ru/cgi-bin/latex.cgi?B. Функция https://www.cyberforum.ru/cgi-bin/latex.cgi?F_{7} — «исключающее ИЛИ». Для нее используется обозначение https://www.cyberforum.ru/cgi-bin/latex.cgi?A\oplus B — функция равна 1, если значения ее аргументов различаются, и равна 0 если они совпадают. Отсюда происходит другое название этой функции — «неравнозначность».
Функция https://www.cyberforum.ru/cgi-bin/latex.cgi?F_{10} в случае равенства аргументов равна 1, а в случае неравенства — равна 0. Поэтому она названа эквивалентностью или равнозначностью. Обозначается эта функция https://www.cyberforum.ru/cgi-bin/latex.cgi?A\sim B или же https://www.cyberforum.ru/cgi-bin/latex.cgi?A\equiv B. Имеются названия еще для трех функций:
  • импликация — https://www.cyberforum.ru/cgi-bin/latex.cgi?F_{14}, обозначается https://www.cyberforum.ru/cgi-bin/latex.cgi?A\rightarrow B или https://www.cyberforum.ru/cgi-bin/latex.cgi?A\supset  B; читается «если https://www.cyberforum.ru/cgi-bin/latex.cgi?A, то https://www.cyberforum.ru/cgi-bin/latex.cgi?B»
  • стрелка Пирса (другое название НЕ-ИЛИ) — https://www.cyberforum.ru/cgi-bin/latex.cgi?F_{9} обозначается https://www.cyberforum.ru/cgi-bin/latex.cgi?A\downarrow B
  • штрих Шеффера (другое название НЕ-И) — https://www.cyberforum.ru/cgi-bin/latex.cgi?F_{15}, обозначается https://www.cyberforum.ru/cgi-bin/latex.cgi?A\mid B.
    Остальные функции используются редко.
Одна и та же функция может быть записана с помощью разных формул. Например штрих Шеффера можно записать и как https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{A}+\bar{B} и как https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{AB}. Такие формулы представляющие одну и ту же функцию называются эквивалентными или равносильными. Для записи формул нет необходимости использовать все функции, например от штриха Шеффера в формулах можно избавиться, выразив его через конъюкцию, дизъюнкцию и отрицание. Существуют наборы логических функций, посредством которых можно выразить любые другие логические функции. Такие наборы называются функционально полными, или базисами.
Также как и штрих Шеффера, через конъюкцию, дизъюнкцию и отрицание можно выразить и другие логические функции двух переменных:
https://www.cyberforum.ru/cgi-bin/latex.cgi?A\rightarrow B=\bar{A}+B
https://www.cyberforum.ru/cgi-bin/latex.cgi?A\sim B=AB+\bar{A}\bar{B}
https://www.cyberforum.ru/cgi-bin/latex.cgi?A\oplus B=A\bar{B}+\bar{A}B
https://www.cyberforum.ru/cgi-bin/latex.cgi?A\downarrow B=\bar{A+B}=\bar{A}\bar{B}
https://www.cyberforum.ru/cgi-bin/latex.cgi?A\mid B=\bar{AB}=\bar{A}+\bar{B}
Формулы содержащие только знаки трёх операций (конъюкции, дизъюнкции и отрицания), а также переменные и скобки, называют булевыми функциями. Справедлива теорема, гласящая, что любая логическая функция может быть представлена в виде булевской формулы. Поэтому набор из конъюкции, дизъюнкции и отрицания образует базис. Множество логических функций, на которых определены эти три операции называются булевой алгеброй. Операции булевой алгебры обычно называют булевыми операциями.
Для булевых операций характерны общие основные свойства:
  • законы ассоциативности (соединительность аргументов):
    (https://www.cyberforum.ru/cgi-bin/latex.cgi?A#https://www.cyberforum.ru/cgi-bin/latex.cgi?B)#https://www.cyberforum.ru/cgi-bin/latex.cgi?C = A#(https://www.cyberforum.ru/cgi-bin/latex.cgi?B#https://www.cyberforum.ru/cgi-bin/latex.cgi?C), где # — любая операция из https://www.cyberforum.ru/cgi-bin/latex.cgi?\vee, https://www.cyberforum.ru/cgi-bin/latex.cgi?\wedge, https://www.cyberforum.ru/cgi-bin/latex.cgi?\oplus, https://www.cyberforum.ru/cgi-bin/latex.cgi?\sim
    https://www.cyberforum.ru/cgi-bin/latex.cgi?A+B+C=(A+B)+C=A+(B+C)
    https://www.cyberforum.ru/cgi-bin/latex.cgi?ABC=(AB)C=A(BC).
    Закон ассоциативности позволяет расставлять скобки произвольным образом в последовательности операций И (или операций ИЛИ) таким образом
    https://www.cyberforum.ru/cgi-bin/latex.cgi?(A\cdot B)\cdot (C\cdot D)=A\cdot (B\cdot C)\cdot D=A\cdot B\cdot C\cdot D
    В действительности можно обойтись без скобок, так как ассоциативный закон гарантирует получение одного и того же результата независимо от того, как сгруппировано предложение.
  • законы коммутативности (переместительность аргументов)
    Коммутационный закон утверждает, что можно переставлять операторы и «от перестановки аргументов результат не изменяется»:
    https://www.cyberforum.ru/cgi-bin/latex.cgi?A#https://www.cyberforum.ru/cgi-bin/latex.cgi?B = A#https://www.cyberforum.ru/cgi-bin/latex.cgi?B, # — любая операция из https://www.cyberforum.ru/cgi-bin/latex.cgi?\vee, https://www.cyberforum.ru/cgi-bin/latex.cgi?\wedge, https://www.cyberforum.ru/cgi-bin/latex.cgi?\oplus, https://www.cyberforum.ru/cgi-bin/latex.cgi?\sim, https://www.cyberforum.ru/cgi-bin/latex.cgi?\downarrow, https://www.cyberforum.ru/cgi-bin/latex.cgi?\mid.
    https://www.cyberforum.ru/cgi-bin/latex.cgi?AB=BA
    https://www.cyberforum.ru/cgi-bin/latex.cgi?A+B=B+A.
  • законы дистрибутивности
    Дистрибутивность конъюнкции и дизъюнкции относительно дизъюнкции, конъюнкции и «исключающему ИЛИ» соответственно:
    https://www.cyberforum.ru/cgi-bin/latex.cgi?A\cdot (B+C)=(A\cdot B)+(A\cdot C),
    https://www.cyberforum.ru/cgi-bin/latex.cgi?A+(B\cdot C)=(A+B)\cdot(A+C),
    https://www.cyberforum.ru/cgi-bin/latex.cgi?A\cdot(B\oplus C)=(A\cdot B)\oplus (A\cdot C)
  • Законы дуальности (де Моргана)
    Формулировка: Если существует операция логического умножения двух и более элементов https://www.cyberforum.ru/cgi-bin/latex.cgi?A\cdot B, то для того чтобы найти обратное от всего суждения https://www.cyberforum.ru/cgi-bin/latex.cgi?AB необходимо найти обратное от каждого элемента и объединить их операцией логического сложения.
    Законы де Моргана можно проверить самостоятельно с помощью таблиц истинности. Законы де Моргана позволяют упростить отрицания формул.
    Два закона булевой алгебры, позволяющие представить дополнение сложного выражения через дополнения его членов в виде
    https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{AB}= \bar{A} + \bar{B}
    https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{A+B}= \bar{A}\bar{B}
    Закон работает и в обратном направлении.
    https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{A}+\bar{B}=\bar{AB}
    https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{A}\bar{B}=\bar{A+B}
    Применяя индукцию и ассоциативность, получим что
    https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{A\cdot B\cdot C\cdot ..}=\bar{A}+\bar{B}+\bar{C}+..
    Дополнение законов де Моргана:
    https://www.cyberforum.ru/cgi-bin/latex.cgi?A\mid B= \bar{A\cdot B}= \bar{A} + \bar{B}
    https://www.cyberforum.ru/cgi-bin/latex.cgi?A\downarrow B= \bar{A+B}= \bar{A} \cdot \bar{B}
    Чтобы построить отрицание формулы, следует изменить знаки и операторы во всей формуле. Например
    https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{\bar{A}+B}=\bar{\bar{A}}+\bar{B}=A\cdot \bar{B}
    Термин «законы де Моргана» часто употребляется применительно к аналогичным соотношениям, используемым в других случаях, например, при операциях над множествами или логическими выражениями.
  • идемпотентность
    https://www.cyberforum.ru/cgi-bin/latex.cgi?A#https://www.cyberforum.ru/cgi-bin/latex.cgi?A = A, https://www.cyberforum.ru/cgi-bin/latex.cgi?A = A#https://www.cyberforum.ru/cgi-bin/latex.cgi?A, #— любая операция из https://www.cyberforum.ru/cgi-bin/latex.cgi?\vee, https://www.cyberforum.ru/cgi-bin/latex.cgi?\wedge.
    https://www.cyberforum.ru/cgi-bin/latex.cgi?A\cdot A=A, https://www.cyberforum.ru/cgi-bin/latex.cgi?A=A\cdot A\cdot A
    https://www.cyberforum.ru/cgi-bin/latex.cgi?A+A=A, https://www.cyberforum.ru/cgi-bin/latex.cgi?A=A+A+A
    (это означает, что в логических формулах в отличии от алгебраических, не бывает степеней и коэффициентов)
  • двойное отрицание
    https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{\bar{A}}=A https://www.cyberforum.ru/cgi-bin/latex.cgi?A=\bar{\bar{A}}
  • закон противоречия
    Закон показывает, что не зависимо от значения https://www.cyberforum.ru/cgi-bin/latex.cgi?A
    https://www.cyberforum.ru/cgi-bin/latex.cgi?A\cdot \bar{A}=0
  • закон исключения третьего
    Закон показывает, что не зависимо от значения https://www.cyberforum.ru/cgi-bin/latex.cgi?A
    https://www.cyberforum.ru/cgi-bin/latex.cgi?A+\bar{A}=1
  • Закон нейтральности
    https://www.cyberforum.ru/cgi-bin/latex.cgi?A+ \bar{B}\cdot B=A
    https://www.cyberforum.ru/cgi-bin/latex.cgi?A\cdot (\bar{B} +B)=A
  • свойства констант
    https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{0} =1
    https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{1} =0
    https://www.cyberforum.ru/cgi-bin/latex.cgi?A+1=1
    https://www.cyberforum.ru/cgi-bin/latex.cgi?A+0=A
    https://www.cyberforum.ru/cgi-bin/latex.cgi?A\cdot 0=0
    https://www.cyberforum.ru/cgi-bin/latex.cgi?A\cdot 1=A
  • другие аксиомы
    https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{A}=0^{A}
    https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{A}=1-A
    https://www.cyberforum.ru/cgi-bin/latex.cgi?A+\bar{A}=A+1=A\sim A=A\rightarrow A=1
    https://www.cyberforum.ru/cgi-bin/latex.cgi?A\cdot \bar{A}=A\cdot 0=A\oplus A=0
    https://www.cyberforum.ru/cgi-bin/latex.cgi?A\oplus 1=A\rightarrow 0=A\sim 0=A\mid A=A\downarrow A=\bar{A}
    https://www.cyberforum.ru/cgi-bin/latex.cgi?A\rightarrow B=\bar{A}+B=AB\oplus A\oplus 1
    https://www.cyberforum.ru/cgi-bin/latex.cgi?A+B=A\oplus B\oplus AB
    https://www.cyberforum.ru/cgi-bin/latex.cgi?A\downarrow B=\bar{A+B}=A\oplus B\oplus AB\oplus 1
    https://www.cyberforum.ru/cgi-bin/latex.cgi?A\mid B=1\oplus AB
  • Свойства операций https://www.cyberforum.ru/cgi-bin/latex.cgi?\leq, https://www.cyberforum.ru/cgi-bin/latex.cgi?min и https://www.cyberforum.ru/cgi-bin/latex.cgi?max
    https://www.cyberforum.ru/cgi-bin/latex.cgi?A\leq 1 https://www.cyberforum.ru/cgi-bin/latex.cgi?min(A,1)=A https://www.cyberforum.ru/cgi-bin/latex.cgi?max(A,1)=1
    https://www.cyberforum.ru/cgi-bin/latex.cgi?0\leq A https://www.cyberforum.ru/cgi-bin/latex.cgi?min(A,0)= 0 https://www.cyberforum.ru/cgi-bin/latex.cgi?max(A,0)=A
    если https://www.cyberforum.ru/cgi-bin/latex.cgi?A+B=B, то https://www.cyberforum.ru/cgi-bin/latex.cgi?A\leq B https://www.cyberforum.ru/cgi-bin/latex.cgi?A+B=max(A,B)
    если https://www.cyberforum.ru/cgi-bin/latex.cgi?A\cdot B=A, то https://www.cyberforum.ru/cgi-bin/latex.cgi?A\leq B https://www.cyberforum.ru/cgi-bin/latex.cgi?A\cdot B=min(A,B)
    https://www.cyberforum.ru/cgi-bin/latex.cgi?A \leq  B тогда и только тогда, когда https://www.cyberforum.ru/cgi-bin/latex.cgi?A\cdot B=A.
Справедливость каждого из этих эквивалентных соотношений может быть легко проверена, достаточно вычислить их левые и правые части на всех возможных наборах значений входящих в них переменных.
Основные эквивалентные преобразования бывают двух типов. Первый — упрощение формул. Он позволяет получать эквивалентные формулы меньшей длины
  • поглощение
    https://www.cyberforum.ru/cgi-bin/latex.cgi?A +AB=A, https://www.cyberforum.ru/cgi-bin/latex.cgi?A(A+B)=A
  • склеивание
    https://www.cyberforum.ru/cgi-bin/latex.cgi?AB+A\bar{B}=A, https://www.cyberforum.ru/cgi-bin/latex.cgi?(A+B)(A+\bar{B})=A
  • неполное склеивание
    https://www.cyberforum.ru/cgi-bin/latex.cgi?AB+A\bar{B}=AB+A\bar{B}+A
  • обобщенное склеивание
    https://www.cyberforum.ru/cgi-bin/latex.cgi?AC+B\bar{C}+AB=AC+B\bar{C}
Второй тип — приведение к дизъюнктивной нормальной форме (ДНФ)

Наборы конъюкция и отрицание, дизъюнкция и отрицание также являются базисами. С помощью отрицания конъюкцию можно выразить через дизъюнкцию и наоборот
https://www.cyberforum.ru/cgi-bin/latex.cgi?A+B=\bar{\bar{A+B}}=\bar{\bar{A}\bar{B}}
https://www.cyberforum.ru/cgi-bin/latex.cgi?AB=\bar{\bar{AB}}=\bar{\bar{A}+\bar{B}}
Существуют и другие базисы, например конъюкция, «исключающее ИЛИ» и константа 1
https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{A}=A\oplus 1
https://www.cyberforum.ru/cgi-bin/latex.cgi?A+B=AB\oplus A\oplus B
Базис может состоять даже из одной функции. Например, и штрих Шеффера, и стрелка Пирса также образуют базисы, поскольку любая из функций — отрицание, конъюкция и дизъюнкция — может быть выражена через них
https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{A}=A\mid A=A\downarrow A
https://www.cyberforum.ru/cgi-bin/latex.cgi?AB=\bar{\bar{AB}}=\bar{A\mid B}=(A\mid B)(A\mid B)=(A\downarrow A)\downarrow (B\downarrow B)
https://www.cyberforum.ru/cgi-bin/latex.cgi?A\rightarrow B=((A\downarrow A)\downarrow B)\downarrow ((A\downarrow A)\downarrow B)
https://www.cyberforum.ru/cgi-bin/latex.cgi?A+B=\bar{A\downarrow B}=(A\downarrow B)\downarrow(A\downarrow B)=(A\mid A)\mid (B\mid B)
https://www.cyberforum.ru/cgi-bin/latex.cgi?A\mid \bar{A}=1
Обобщения
На данном множестве https://www.cyberforum.ru/cgi-bin/latex.cgi?\Re с n=2 можно задать две функции не зависящие от аргументов (0, 1), четыре функции от одного аргумента ( https://www.cyberforum.ru/cgi-bin/latex.cgi?A, https://www.cyberforum.ru/cgi-bin/latex.cgi?B, https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{A}, https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{B}) и десять функций от двух аргументов ( https://www.cyberforum.ru/cgi-bin/latex.cgi?A\vee B, https://www.cyberforum.ru/cgi-bin/latex.cgi?A\wedge B, https://www.cyberforum.ru/cgi-bin/latex.cgi?A\rightarrow B, https://www.cyberforum.ru/cgi-bin/latex.cgi?B\rightarrow A, https://www.cyberforum.ru/cgi-bin/latex.cgi?A\sim  B, https://www.cyberforum.ru/cgi-bin/latex.cgi?A\oplus B и другие), представленных в таблице 8.3, однако все функции могут быть получены через суперпозицию трех операций И, ИЛИ, НЕ.
Полный набор логических функций для переменных A и B
перемен-
ные
функции
https://www.cyberforum.ru/cgi-bin/latex.cgi?Ahttps://www.cyberforum.ru/cgi-bin/latex.cgi?B0https://www.cyberforum.ru/cgi-bin/latex.cgi?A\wedge Bhttps://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{A\rightarrow B}https://www.cyberforum.ru/cgi-bin/latex.cgi?Ahttps://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{B\rightarrow A}https://www.cyberforum.ru/cgi-bin/latex.cgi?Bhttps://www.cyberforum.ru/cgi-bin/latex.cgi?A\oplus Bhttps://www.cyberforum.ru/cgi-bin/latex.cgi?A\vee Bhttps://www.cyberforum.ru/cgi-bin/latex.cgi?A\downarrow Bhttps://www.cyberforum.ru/cgi-bin/latex.cgi?A\sim Bhttps://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{B}https://www.cyberforum.ru/cgi-bin/latex.cgi?B\rightarrow Ahttps://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{A}https://www.cyberforum.ru/cgi-bin/latex.cgi?A\rightarrow Bhttps://www.cyberforum.ru/cgi-bin/latex.cgi?A\mid B1
000000000011111111
010000111100001111
100011001100110011
110101010101010101
перемен-
ные
суперпозиция функций через И, ИЛИ, НЕ
https://www.cyberforum.ru/cgi-bin/latex.cgi?Ahttps://www.cyberforum.ru/cgi-bin/latex.cgi?B0https://www.cyberforum.ru/cgi-bin/latex.cgi?ABhttps://www.cyberforum.ru/cgi-bin/latex.cgi?A\bar{B}https://www.cyberforum.ru/cgi-bin/latex.cgi?Ahttps://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{A}Bhttps://www.cyberforum.ru/cgi-bin/latex.cgi?Bhttps://www.cyberforum.ru/cgi-bin/latex.cgi?A\bar{B}+\bar{A}Bhttps://www.cyberforum.ru/cgi-bin/latex.cgi?A+Bhttps://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{A+B}https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{A}\bar{B}+ABhttps://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{B}https://www.cyberforum.ru/cgi-bin/latex.cgi?A+\bar{B}https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{A}https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{A}+Bhttps://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{AB}1
Таблица 8.4
Опираясь на этот математический инструментарий, логика высказываний изучает высказывания и предикаты. Также вводятся дополнительные операции, такие как эквивалентность https://www.cyberforum.ru/cgi-bin/latex.cgi?\sim («тогда и только тогда, когда»), импликация https://www.cyberforum.ru/cgi-bin/latex.cgi?\rightarrow («следовательно»), «исключающее ИЛИ» https://www.cyberforum.ru/cgi-bin/latex.cgi?\oplus, штрих Шеффера https://www.cyberforum.ru/cgi-bin/latex.cgi?\mid , стрелка Пирса https://www.cyberforum.ru/cgi-bin/latex.cgi?\downarrow и другие.
Все указанные операции, за исключением одноместных (НЕ и Тождественность), выполняются при двух и более переменных на входе, и в каждом случае получается только один выход. Одноместные операции характеризуются одним входом и одним выходом.
Логика высказываний послужила основным математическим инструментом при создании компьютеров. Она легко преобразуется в битовую логику: истинность высказывания обозначается одним битом (0 — ЛОЖЬ, 1 — ИСТИНА); тогда операция ¬ приобретает смысл вычитания из единицы; https://www.cyberforum.ru/cgi-bin/latex.cgi?\wedge— немодульного сложения; https://www.cyberforum.ru/cgi-bin/latex.cgi?\vee – умножения; https://www.cyberforum.ru/cgi-bin/latex.cgi?\sim — равенства; https://www.cyberforum.ru/cgi-bin/latex.cgi?\oplus — («исключающее ИЛИ» – XOR); https://www.cyberforum.ru/cgi-bin/latex.cgi?\mid — непревосходства суммы над 1 (то есть https://www.cyberforum.ru/cgi-bin/latex.cgi?A\mid B = (A + B) \leq  1) и так далее.

Впоследствии булева алгебра была обобщена от логики высказываний путём введения характерных для логики высказываний аксиом.
Свойства логических операций
  1. https://www.cyberforum.ru/cgi-bin/latex.cgi?A\cdot \bar{A}=A\cdot 0=A\oplus A = 0
  2. https://www.cyberforum.ru/cgi-bin/latex.cgi?A+\bar{A}=A+1=A\sim A =A\rightarrow A = 1
  3. https://www.cyberforum.ru/cgi-bin/latex.cgi?A+A=A\cdot A=A\cdot 1=A+0=A\oplus 0 = \bar{\bar{A}}=A
  4. https://www.cyberforum.ru/cgi-bin/latex.cgi?A\oplus 1 = A\rightarrow 0 = A\sim 0 = A\mid A = A\downarrow A = \bar{A}
  5. https://www.cyberforum.ru/cgi-bin/latex.cgi?A\oplus B=\bar{A}B+A\bar{B}= (A+B)(\bar{A}+\bar{B})=\bar{(\bar{A}+B)(A+\bar{B})}=\bar{(\bar{A}+B)}+\bar{(A+\bar{B})}
  6. https://www.cyberforum.ru/cgi-bin/latex.cgi?A\sim B=\bar{A\oplus B} =AB+\bar{A}\bar{B}=(A+\bar{B})(\bar{A}+B)
  7. https://www.cyberforum.ru/cgi-bin/latex.cgi?A+\bar{BC}=A+\bar{B}+\bar{C}
  8. https://www.cyberforum.ru/cgi-bin/latex.cgi?A\rightarrow B= \bar{A} +B=\bar{A\bar{B}}=((A\cdot B)\oplus A)\oplus 1
  9. https://www.cyberforum.ru/cgi-bin/latex.cgi?A\rightarrow B= \bar{A} +B= B+\bar{A}=\bar{\bar{B}}+\bar{A}=\bar{B}\rightarrow \bar{A}
  10. https://www.cyberforum.ru/cgi-bin/latex.cgi?A\rightarrow (B\rightarrow A)=1
  11. https://www.cyberforum.ru/cgi-bin/latex.cgi?(A\rightarrow (B\rightarrow C))\rightarrow((A\rightarrow B)\rightarrow(A\rightarrow C))=1
  12. https://www.cyberforum.ru/cgi-bin/latex.cgi?(\bar{B}\rightarrow\bar{A})\rightarrow((\bar{B}\rightarrow A)\rightarrow B))=1 если сделать замену https://www.cyberforum.ru/cgi-bin/latex.cgi?A=\bar{B} то можно получить https://www.cyberforum.ru/cgi-bin/latex.cgi?(A\rightarrow\ B)\rightarrow((A\rightarrow\bar{B})\rightarrow\bar{A})=1
  13. https://www.cyberforum.ru/cgi-bin/latex.cgi?(\bar{B}\rightarrow\bar{A})\rightarrow(A\rightarrow B)=1
  14. https://www.cyberforum.ru/cgi-bin/latex.cgi?\bar{\bar{A}}\rightarrow A=1
  15. https://www.cyberforum.ru/cgi-bin/latex.cgi?AB\rightarrow A=1
  16. https://www.cyberforum.ru/cgi-bin/latex.cgi?AB\rightarrow B=1
  17. https://www.cyberforum.ru/cgi-bin/latex.cgi?(A\rightarrow B)\rightarrow(\bar{BC}\rightarrow\bar{AC})=1
  18. https://www.cyberforum.ru/cgi-bin/latex.cgi?A\rightarrow(B\rightarrow AB)=1
  19. https://www.cyberforum.ru/cgi-bin/latex.cgi?(A\rightarrow C)\rightarrow((B\rightarrow C)\rightarrow((A+B)\rightarrow C))=1
  20. https://www.cyberforum.ru/cgi-bin/latex.cgi?A\cdot B=\bar{A\rightarrow\bar{B}}
  21. https://www.cyberforum.ru/cgi-bin/latex.cgi?A+B=\bar{A}\rightarrow B
Существуют методы упрощения логической функции: например, Карта Карно, метод Квайна — Мак-Класки.
Миниатюры
Электронный учебник   Электронный учебник   Электронный учебник  

Электронный учебник   Электронный учебник   Электронный учебник  

Электронный учебник  
Изображения
 
5
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
14.11.2013, 07:10

Какой учебник выбрать для изучения ассемблера?
Решил выучить ассемблер, посоветовали скачать что-нить отсюда http://asm-book.narod.ru/index.html ...

Подскажите, пожалуйста,учебник по асму.
Подскажите, пожалуйста, ОЧЕНЬ простой и современный учебник по ассемблеру.

Учебник MASM32(под win)
Извините, если тема соблюдает не все правила, но меня интересует определённый учебник.На сайте...

Посоветуйте учебник и IDE
Посоветуйте пожалуйста хороший учебник и IDE. Выбор встал между RadASM и WinAsm studio. Что лучше?...

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


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Закрытая тема Создать тему
Новые блоги и статьи
Транслитерация текста с кириллицы на латиницу (вариант №5)
Maks 17.11.2026
Дабы оставить позади все споры о том, какая буква каким образом должна транслитерироваться на латиницу - решил таки доработать данное решение и довести его до мало-мальски логического завершения. . . .
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой. Но использовать несколько программ не удобно. Искал другие. . .
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской) Options Preferences General Language
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент". В данной функции нет апострофов,. . .
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы. Карта этого меню приложена ниже. Нужный пункт выделен красным. Сервис Настройки Поведение
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки. Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён". Изменено отображение буквы Й. Добавлена. . .
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
Часы с термометром и праздничным календарем
yariko 12.11.2026
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru