- •Оглавление
- •1. Информация, ее представление и измерение
- •2. Общая характеристика процессов сбора, передачи и обработки информации
- •2.1. Системы счисления и действия в них
- •2.2. Общая характеристика процессов передачи информации
- •2.3. Кодирование и шифрование информации
- •2.4. Компьютерные вирусы
- •3. Модели решения функциональных и вычислительных задач
- •3.1. Модели и моделирование
- •3.2. Основные свойства модели и моделирования
- •Моделирование – есть метод системного анализа.
- •3.3. Классификация видов моделирования
- •3.4. Компьютерное моделирование
- •3.5. Функции алгебры логики
- •3.6. Булева алгебра. Функциональная полнота
- •8. Закон поглощения
- •9. Закон Де Моргана
- •3.7. Минимизация функций алгебры логики
- •4. Программные средства реализации информационных процессов
- •5. Технические средства реализации информационных процессов
- •6. Алгоритмизация и программирование
- •6.2. Данные, типы данных, структуры и обработка
- •7. Архитектура эвм. Локальные и глобальные сети.
- •7.1. Архитектура эвм
- •7.2. Cеть передачи данных
- •7.3. Аппаратные средства сети
- •7.4. Локальная вычислительная сеть
- •7.5. Топология сети
- •7.6. Глобальная вычислительная сеть
- •7.7. Сетевая модель osi
- •7.8. Стек протоколовTcp/ip
- •8. Программное обеспечение
- •8.1. Классификация и основные характеристики по
- •8.2. Структура технического обеспечения
- •8.3.Состав операционной системы и ее основные функции
- •9. Технология программирования
- •9.1. Организация данных в эвм
- •9.2. Стеки и очереди
- •9.3. Графы
- •9.4. Деревья
- •10. Базы данных
- •10.1. Основные понятия
- •10.2. Модели данных в субд
- •Реляционные базы данных
- •Выбор типа поля
- •10.3. Основные понятия реляционной модели
- •11. Объектно – ориентированное программирование
- •11.1. Основные положения ооп
- •11.2. Инкапсуляция
- •11.3. Полиморфизм
- •11.5. Наследование
- •Литература
3.6. Булева алгебра. Функциональная полнота
Определение. Алгеброй над множеством логических функций с двумя бинарными операциями, обозначаемыми как логическое умножение & и логическое сложение v и одной унарной операцией ( отрицанием )
называется булевой алгеброй. Будем обозначать ее символом B.
Рассмотрим свойства булевой алгебры.
Замкнутость
для A и B B
A v B B
A & B B
Коммутативность
A & B = B & A
A v B = B v A
3. Ассоциативность
A v ( B v C) = (A v B) v C
Дистрибутивность
A & ( B v C) = (A & B) v (A & C)
A v ( B & C) = (A v B) & (A v C)
Идемпотентность
A v A = A & A = A.
Булева алгебра содержит элементы 0,1 , такие что для всякого
элемента A B справедливо:
A v 0 = A, A v 1 = 1
A & 0 = 0, A & 1 = A.
7. Для каждого элемента A B существует элемент , такой что
A v =1
A & =0.
8. Закон поглощения
A & (A v B) = A v A & B = A.
9. Закон Де Моргана
3.7. Минимизация функций алгебры логики
Введем понятие конечного автомата, как некоторой абстрактной системы, характеризующейся конечным числом состояний. Работа такого автомата напрямую связана с реализацией соответствующей ему логической функции в виде схемы или программы и поступающими из вне данными в каждый такт времени. На основе теории конечных автоматов организуется работа управляющих программ ЭВМ.
Работа конечного автомата может быть полностью описана с помощью следующей системы функций алгебры логики [7]:
y1= f1 (x1 ... xn )
y2= f2 (x1 ... xn )
...
ym= fm (x1 ... xn )
Здесь Pi = ( X1, X2, ...,Xn ); Qj = ( y1, y2, ...,ym ) - соответственно входное и выходное слово. Работа автомата может быть задана либо в виде конечных таблиц, либо в виде аналитической записи функций fi .
Проблема полноты системы функций эквивалентна проблеме выбора стандартного набора элементов, из которого будет строиться автомат, при этом все функции fi должны быть выражены через базисные функции. Уменьшение числа функций в базисе приводит к уменьшению стандартных элементов, на которых строится схема, однако, при этом увеличивается общее число элементов схемы. Возникает задача о “простейшем” представлении логических функций через систему базисных функций. Для этого используют методы минимизации:
- метод вынесения за скобки;
- метод неопределенных коэффициентов;
- метод с использованием карт Карно;
- метод Мак - Класки;
- метод Блэка.
Рассмотрим метод минимизации совершенной дизъюнктивной нормальной формы (СДНФ) с помощью карт Карно. Карта Карно - это диаграмма, состоящая из 2n квадратов, где n - число переменных. Клетка карты - одна из возможных конъюнкций, входящих в СДНФ. Минимизация на основе карт Карно осуществляется путем локализации на карте прямоугольных областей из числа клеток кратного 2.
Для работы с картой необходимо по таблице истинности составить СДНФ, затем для каждой элементарной конъюнкции проставить 1 в соответствующие клетки карты. Затем единицы объединяются таким образом, чтобы минимизировалось число логических сложений, умножений или отрицаний, что важно для экономного конструирования ЭВМ.
Рассмотрим карты Карно.
Для двух переменных: Для трех переменных:
a a
c
b
b
Для четырех переменных:
a
c
c d
d
b
Пример. Для логической функции заданной таблицей
-
x1
x2
x3
f
1
1
1
1
1
1
0
1
1
0
1
1
1
0
0
1
0
1
1
1
построить карту Карно и на ее основе минимизировать функцию.
Решение. Построим карту согласно описанным выше правилам.
x1
1 1 f = x1 v x2 & x3
x2 1 1 1
x3
Рассмотрим пример представления простейшей функции картой Карно
a
c 1 1
c 1 1 d
f = b
1 1 d
1 1
b
Рассмотрим построение логической схемы для функции вида:
f1 = V2 & V4 v V3 & V1 & V2 v V3 & V4 & V1.
V1
V2
V3
V4
& & & & &
& &
&
&
1
1
f1