Тема 2.1. Элементы математической логики

Понятие алгебры логики. Основные логические операции и логические элементы.

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

Область алгебры логики состоит из множества высказываний (обозначаются A, B, C…). Высказывание – это законченное предложение, которое может иметь два значения истинности (t or f).

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

Операции алгебры логики и логические элементы:

1) Логическое умножение (конъюнкция, операция и). F=A^B=A&B=A*B=AB;

На выходе сигнал соответствует логической единице только тогда, когда на всех входах одновременно будет сигнал логической единицы.

Разрешаемым уровнем схемы i является уровень логической единицы.

Логическая функция от n переменных в таблице истинности будет иметь 2ⁿ строк.

На выходе схемы сигнал соответствует 0 только тогда, когда на всех входах одновременно будет сигнал логического нуля. Разрешающим для схемы или является уровень логического нуля.

2) Равнозначность (или-не).

3) Отрицание конъюнкции.

4) Отрицание дизъюнкции.

Основные законы логики

2.2 Формулы логических функций и их использование для синтеза логических схем.

Формы логических функций.

ACBvAC1BvACBA=ACBvACBvACB=ACvAB= AB*AC (дизъюнктивная) =(AvC)*(AvB) (конъюнктивная).l

PF могут быть выражены различными логическими формулами благодаря возможности проведения над ними эквивалентных преобразовании. На практике наиболее удобными для представления PF оказываются дизъюнктивные и конъюнктивные формы.

Эти формы представляют собой дизъюнкции элементарных конъюнкций или конъюнкции элементарных дизъюнкций.

Конъюнкция (дизъюнкция) любого числа двоичных переменных A, B, C… называется элементарное если со множителями (слагаемыми) в ней являются либо одиночные аргументы, либо их отрицание. Например:

Элементарные конъюнкции и дизъюнкции: (AvB), (AvBvD), (AvDvC)

Конъюнкции и дизъюнкции, которые не являются элементарными: AvB, AvBvC, AvBvB и конъюнкции.

Дизъюнктивной нормальной формой (ДНФ ПФ) называется дизъюнкция любого числа элементарных конъюнкций.

Например: F=ABCvADvBvCD

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

Примеры рангов: AB- конъюнкция 2-го ранга, AvB – дизъюнкция 2-го ранга, ABC – 3-го ранга.

Совершенной ДНФ (сднф) ПФ, имеющий n аргументов называется такая форма, в которой все конъюнкции имеют ранг n.

Например: F = ABCvABCvABC

ПФ могут быть заданы словестно, в виде таблицы истинности, алгебраическим выражением. По словестному описанию составляют таблицу истинности, а затем записывают СДНФ ПФ.

СДНФ переключательной функции записывается по таблице истинности в следующей последовательности:1 из таблицы истинности выделяются строки, в которых функция равна единице. 2 записываются составляющие формулы в виде конъюнкции переменных или их отрицание. Если переменная в данном наборе равна единице, то она входит в формулу как не отрицаемая. 3 конъюнкции объединяют знаком дизъюнкции.

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

F=ABCvABCvABCvABC=ABvACvBC

| | |

Задача: записать ПФ устройства, функционирующего по правилу: сигнал на выходе равен единице, если хотя бы на 3 входах из 4 присутствует уровень 1.

Конъюнктивные формы представления формы ПФ используются реже, чем дизъюнктивные.

Конъюнктивной нормальной формой (КНФ ПФ) называется конъюнкция элементарных дизъюнкций.

Например:!

Совершенной КНФ (СКНФ) РФ имеющей n аргументов называется такая форма, в которой все дизъюнкции имеют ранг n.

Например:

2.3. Логические элементы и схемы, классификация логических устройств.

1. Функционально полные системы логических функций.

Последовательная схема состоит из логических и запоминающих элементов(триггеров).

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

Используются две модели цифровых автоматов с памятью:

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

2. Абстрактная модель. Применяется при теоритическом рассмотрении автомата. Абстрактным автоматом называют дискретный преобразователь информации с конечным входным алфавитом Z, конечным выходным алфавитом W, конечным множеством внутренних состояний А и двумя характеристическими функциями(16 стр. внизу).

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

В зависимости от способа определения выходных сигналов различают два типа автоматов:

1. Автоматы Мура. Описываются системой уравнений. В автоматах Мура выходной символ не зависит явно от входного символа Z от Т, а определяется внутренним состоянием в момент времени Т.

2. Автоматы Мили. Описываются системой уравнений. В автомате Мили выходной сигнал в момент времени Т зависит как от внутреннего состояния автомата в момент Т так и от входного сигнала в момент Т.

Поиск по сайту: