Функционально полные системы ПФАЛ

 

Функционально полной системой (ФПС) или базисом  ПФПФ называют систему (множество, совокупность) ПФПФ F_1,F_2, F_3….. F_n, c помощью которых может быть представлена любая ФАЛ.

Функционально полными системами являются следующие базисы (с их помощью можно представить все любые ФАЛ из табл.2)

 

Базис 1 И, ИЛИ, НЕ – основной т.к. любое сложения ПФ может быть заполнена в виде СДНФ или СКНФ

 

Базисы могут быть

А) избыточными: (можно исключить из него некоторые функции) (И, ИЛИ,НЕ)

Б) минимальными: (И-НЕ) и (ИЛИ-НЕ) т.е. содержит минимальное количество переменных в термах. Она не допускает никаких допущений.

В) нормальными: (И,НЕ и ИЛИ, НЕ), т.к. удаление любой из функций, составляющих базис; ФПС превращается в неполную. Проблема представления ФАЛ сводится к:

-выбору базиса

-формы наиболее экономного представления этих функций

НДФ и НКФ с точки зрения экономичности предпочтительнее СДКФ и СКНФ, то они являются неподвижными.

Упрощение сложных ФАЛ осуществляется по законам, правилам и аксиомам алгебры логики.

 

 

Минимизация ПФАЛ.

    

Минимальной формой представления ПФ называюттакую, которая не допускает дальнейшее упрощение

Минимизация ПФАЛ – это процесс получения минимальной нормальной формы.

При минимизации исходят из требования минимальных затрат оборудования при физической реахлизации ПФАЛ, т.к. каждой элементарной логической функции соответствует определенной логической элемент.

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

 

Методы:

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

- метод Кванта – для ПФ невысокого порядка при условии, что исходные функции заданы в СДНФ.

- минимизирующих карт Карно – для функций небольшого числа переменных

- метод диаграмм Вейча – разновидность метода Карно.

Метод последовательного исключения переменных.

Основная задача: аналитически заданную логарифмическую функцию свести к минимальной форме в заданным базисе.

Математический аппарат: законы правила, аксиомы и следствия алгебры логики.

Опасность: тупиковая форма – форма логической функции, которая больше не упрощается. Она не всегда минимальна.

 

 

Диаграмма Вейча

 

Количество клеток K = 2ⁿ  n – число аргументов.

	Y              Y

  

X*Y	X*Y
X 2-х местная функция X*Y	X*Y

Каждому кортежу своя клетка

Содержимое клетки – конъюнкция переменных

 

 

Y              Y

     Пример 1.         F(X,Y) = XY^XY

=Х

                                                                            

X                                                                     1	Охватываем единицу четырехугольным контуром соотв. Склеиванию конституент единицы по некоторой переменной. 1
X 0	0

 

Д-но:  F(X,Y) = X(Y^Y)

 

 

Пример 2.                 F(x,y) =XY^ XY^ XY^XY=(XY^ XY)(XY^ XY) =            X(Y^Y)^Y(X^X)=X^Y

 

 

X                                                                 1	Здесь можно склеивать по X и по Y ( ) Поэтому F(x,y) = x^y 1
X 0	1

 

 

3-x местная функция

Боковая поверхность развертки цилиндра

	Y          Y          Y        Y

111 XYZ	110 XYZ	100 XYZ	101 XYZ
011 XYZ	010 XYZ	000 XYZ	001 XYZ

X

 

Можно инвертировать как развертку боковой поверхности цилиндра.

Поэтому единицу в крайнем левом и правом столбцах находятся рядом.

 

 

X

Допускается склеивать 2,4,8 и т.д. рядом стоящих единиц. В общем числе единицу, охватываемых одним контуром и образующих одну простую импликанту, удовлетворяет условию 

           A= log₂Q

 

Где Q – число рядом стоящих единиц, образующих импликатуру.

  А- целое число, показывающее, на сколько переменных в импликанте меньше, чем в конституенте 1.

 

 

Импликатой ФАЛ

F(*) называют любую другую ФАЛ q(*) меньшей сложности, которая на тех наборах аргументов, на которых F(*)=0, обязательно обращается в 0, (т.е. если F(*)=0,то q(*)=0); а на тех наборах аргументов, на которых F(*)=1, импликанта обращается либо в 0, либо в 1. т.е. если F(*)=1,то q(*)=0^q(*)=1

 

Если а=1, то Q=2 – охватывается контуром две единицы.

Если а=2, то Q=4 – четыре единицы.

 

В первом случае в импликанте будет на одну, а во втором на два аргумента меньше, чем в конституенте единицы.

 

Пример 3. F(x,y,z) = XYZ^ XYZ^ XYZ^ XYZ^ XYZ

   

			Один контур охватывает две «1»  импликанта = 1     Т.к. XYZ^XYZ=XY(Z^Z)=XY

	0	1	XY 1
1 X 1	0	0	1

Z          Z            Z             Z

Y           Y            Y             Y

 

Второй контур охватывает четыре «1». Импликанта = Z

 

Н

в

Д-но:

                       XY YZ      = XZ м.в. YZ  тогда

 

XZ^YZ^ XZ^YZ=Z(X^X)^Z(Y^Y)=Z^Z=Z

 

В итоге F (X,Y,Z) = XY^Z

 

 

Метод диаграмм Вейча не требует приводить ФАЛ к СДНФ (в отличии, например, от метода Карно)

На диаграмме можно наносить произвольно ДНФ, но при этом:

                                

            - конституента «1» наносится одной 1;

            - импликанта с недостающим одним аргументом – двумя рядом стоящими

            - если недостает 2 переменных, то помещают рядом 4 единицы.

 

           

   

 

	1	1	0   F(X,Y,Z)=XY^XY^YZ
0 X	0	1	1

Z          Z            Z             Z

Y           Y            Y             Y

 

Метод Кванта

Запись ПФ в универсальных базах

Анализ и синтез КС

Синтез ЦА.

 

 

Домашнее задание:

Литература

«Сборник практических и лабораторных работ»

Приложение В, Г

Изучить законы и правила алгебры логики

Подготовиться к выполнению РГР.