Алгоритм построения СКНФ по таблице истинности

(Совершенная Конъюнктивная Нормальная Форма)

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

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

3. Все полученные дизъюнкции связываем операциями конъюнкции.

Для таблицы истинности xor это будет (A || B) &&(!A ||!B)

Упражнения. Записать в нормальной форме следующие операции:

Импликация	Эквиваленция
Штрих Шеффера	Стрелка Пирса

 

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

ВХОД ВЫХОД A B A NAND B

ВХОД ВЫХОД A B A NOR B

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

Из вентилей строятся так называемые интегральные схемы (по-английски chips) – это набор вентилей, соединённых проводами и такими радиотехническими элементами, как сопротивления, конденсаторы и индуктивности, которые знакомы Вам из курса физики. Каждая интегральная схема тоже имеет свои входы и выходы (их называют внешними контактами схемы) и реализует какую-нибудь функцию узла компьютера. В специальной литературе интегральные схемы, которые содержат порядка 1000 вентилей, называются малыми интегральными схемами (МИС), порядка 10000 вентилей – средними (СИС), порядка 100000 – большими (БИС), а число вентилей в сверхбольших интегральных схемах (СБИС) исчисляется уже миллионами.

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

Дадим представление о количестве вентилей в различных электронных устройствах. Например, для того, чтобы реализовать схему самых простых электронных часов, необходимо порядка 1000 вентилей, из 10000 вентилей уже можно собрать простейший центральный процессор, а, например, центральные процессоры современных персональных ЭВМ реализуются на интегральной схеме, состоящей уже из десятков миллионов вентилей. Так, интегральная схема центрального процессора Pentium 4 содержала уже более 40 миллионов транзисторов (около 15 миллионов вентилей). Сейчас на одной пластинке кремния обычно создают не один, а несколько почти независимых друг от друга центральных процессоров, собранные на базе таких интегральных схем компьютеры называются многоядерными.

Полусумматор и сумматор

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

Неполный сумматор (полусумматор) — логическая схема имеющая два входа и два выхода (двухразрядный сумматор, бинарный сумматор). Позволяет вычислять сумму , где и — это разряды двоичного числа, при этом результатом будут два бита , где — это бит суммы по модулю, а — бит переноса (carry-in bit).

a b С S

Полусумматор собран из сумматора по модулю 2 с добавлением элемента AND для получения сигнала переноса; его действие можно описать следующим логическим выражением:

S = a XOR b; С = a AND b,

где a и b – содержимое входов, S – содержимое выхода «сумма», С – содержимое выхода «перенос».

Теперь, если реализовать этот двоичный сумматор (полусумматор) в виде интегральной схемы (ИС), то она будет иметь не менее 7-ми внешних контактов (см. рис. 1.). Это входные контакты a и b, выходные s и с, один контакт для подачи тактовых импульсов (о них мы уже говорили, когда объясняли работу вентилей), два контакта для подачи электрического питания (ясно, что без энергии ничего работать не будет) и, возможно, другие контакты.

Рисунок 1. Пример ИС двоичного сумматора

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

Полный сумматор

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

Каскадный сумматор

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

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

При сложении двух чисел в -том разряде складываются , и входной бит переноса (carry-in bit) . Младший разряд суммы записывается в -й разряд ответа (), а старший становится выходным битом переноса (carry-out bit) и используется при сложении в следующем разряде.

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

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

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

Ясно, что скорость работы интегральной схемы напрямую зависит от частоты прихода тактовых импульсов, называемой тактовой частотой схемы. У современных ЭВМ не очень высокой производительности тактовые импульсы приходят на схемы основной памяти с частотой несколько сотен миллионов раз в секунду, а на схемы центрального процессора – ещё примерно в 10 раз чаще. Это должно дать Вам представление о скорости работы электронных компонент современных ЭВМ.

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