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

составления СДНФ
Основные законы булевой алгебры
Логические основы ЭВМ.
Алгебра Дж. Буля и ее применение в теории и практике информатики
Процессоры
Заключение

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

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

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

x+1=1; x*0=0 -//-//-//-//-//-
2. x+x=x; x*x=x Идемпотентности
3. (x`)`=x Двойного отрицания
4. x+y=y+x; x*y=y*x Коммутативности
5. x+x*y=x*(x+y)=x; x+x`* y=x+y; x*(x`+y)=x*y Поглощения
6. (x+y)`-x`*y`; (x*y)`=x`+y` Моргана
7. (x+y)+z=x+(y+z)=x+y+z; (x*y)* z=x*(y*z)=x*y*z Ассоциативности
8. x+y*z=(x+y)*(x+z); x* (y+z)=x*y+x*z Дистрибутивности 

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

логический 0 (значение "ложь") появляется только тогда, когда на все его выходы (два и более) поданы сигналы логического 0; во всех остальных случаях на выходе появляется логическая 1 (значение "истина"). Этот вентиль реализует логическую операцию ИЛИ и имеет аналогичную с ней таблицу истинности.  
А2 0 1 0 1
Выход В 0 1 1 1
Элемент НЕ-И (штрих Шеффера).
Электронная логическая схема, в которой выходной сигнал имеет уровень логической 0 (ложь) только тогда, когда на всех ее входах действуют сигналы логической 1. Во всех других случаях на его выходе появляется логическая 1.
А2 0 1 0 1
Выход В 1 1 1 0
Вентиль НЕ-И эквивалентен И с инвертированным выходом.
Элемент ИЛИ-НЕ(стрелка Пирса).
Электронная логическая схема, на выходе у которой появляется логическая 1 только тогда, когда на все ее входы поданы сигналы логического 0, а в любых других случаях на выходе схемы действует уровень логического 0.
А2 0 1 0 1
Выход В 1 0 0 0
Практически любые схемы могут быть построены на одних только элементах ИЛИ-НЕ.
Элемент НЕ (NOT gate).
Электронный логический вентиль, инвертирующий входной сигнал, т.е. преобразующий логический 0 в логическую 1 и наоборот.
Выход В И Л 

с которой имеют дело различного рода автоматизированные информационные системы, обычно называется дан­ными., а сами такие системы — автоматизированными системами обработки данных (АСОД). Различают исходные (входные), промежуточные и выходные данные.
Данные разбиваются на отдельные составляющие, называемые элементарными данными или элементами данных. Употребляются элементы данных различных типов. Тип данных (элементарных) зависит от значений, которые эти данные могут принимать.
В современной безбумажной информатике среди различных типов элементарных данных наиболее употребительными являются целые и вещественные числа, слова (в некотором подалфавите байтового алфавита) и так называемые булевы величины. Первые два типа величин нуждаются в пояснении только в связи с конкретными особенностями их представления в современных ЭВМ.
Прежде всего различают двоичное и двоично-десятичное представления чисел. В двоичном представлении используется двоичная система счисления с фиксированным числом двоичных раз­рядов (чаще всего 32 или, для малых ЭВМ, 16 разрядов, включая разряд для представления знака числа). Если нулем обозначать плюс, а единицей — минус, то 00001010 означает целое число +(23+2l)= + l0, а 10001100— число— (23 + 22) = —12 (для простоты взято 8-разрядное представление). Заметим, что знак числа в машинном представлении часто оказывается удобным ставить не в начале, а в конце числа.

то подобным образом могут быть закодированы условия и решения задач ил любой области знаний. Если число таких задач конечно (хо­тя, может быть, и очень велико), то существуют максимальная длина т кода условий этих задач и максимальная длина n кода nх решений. В таком случае решения всех данных задач (в двоичном коде) могут быть получены из их условий с по­мощью некоторой системы булевых функций yi=fi(xi, х2, ... ..., xm) (i == 1, ..., n). В свою очередь все эти функции могут быть выражены через элементарные булевы операции конъюнк­ции, дизъюнкции и отрицания.
Существуют различные способы представления булевых ве­личин (двоичных цифр) в виде тех или иных физических (обыч­но электрических) сигналов (высокое и низкое напряжение, им­пульсы тока разной полярности и т. п.).
Выбрав форму представления (двоичных) сигналов, можно построить элементарные устройства, называемые обычно логическими вентилями (или логическими элементами), которые реали­зуют элементарные булевы операции. Иными словами, выходные
сигналы этих устройств представляют собой элементарные булевы функции (результат выполнения элементарных булевых операций) от входных сигналов, как это показано на рис. 1.

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

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