Минимизация формул алгебры логики

Формулы алгебры логики, полученные с помощью таблиц истинности или другими способами, как правило, подлежат минимизации – упрощению.

Например, формулу

можно упростить, используя закон де Моргана для освобождения от отрицаний:

Минимизацию можно осуществить двумя группами методов.

 

Алгебраическими методами минимизации

Он предполагает использование законов алгебры логики, выраженных формулами:

закон исключенного третьего

закон противоречия

закон двойного отрицания

две формы закона де Моргана

A + A&B = A закон поглощения

A&B + A& = A закон склеивания

 

A+A + A

A&A = A две формы закона идемпотентности

а также формул преобразования логических операций:

импликации

эквивалентности

Пример:

Как видно, минимизация алгебраическими методами не всегда проста.

 

Табличными методами минимизации

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

Возьмем любую логическую функцию двух аргументов:

X	Y	F

Составляем сумму произведений аргументов тех строк, значение функции в которых истинно:

F =

Составляем таблицу, называемую диаграммой Вейча для функции двух аргументов:

 

X

Y

Записываем единицы в тех ячейках таблицы, которые соответствуют произведениям:

X

Y

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

F = =

При расстановке слагаемых так:

X

Y

получаем следующую минимальную форму:

F = X

При такой расстановке слагаемых:

X

Y

Имеются два объединения, которые соответствуют следующей минимальной форме:

Если таблица полностью заполнена единицами:

1

X

 

Y

То после объединения четырех соприкасающихся ячеек получаем следующую минимальную форму:

F = 1

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

Диаграмма Вейча для функции трех аргументов имеет вид:

Z

 

X

 

Y

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

Z

	1

X

 

Y

В этом случае имеются три объединения, образующие следующую минимальную форму:

F = X&Y + Y&Z + &Z

При объединении четырех соприкасающихся ячеек остается один общий для них аргумент:

Z

X

 

Y

В этом случае:

F = Y

Можно объединять ячейки, находящиеся на противоположных концах диаграммы:

Z

X

 

Y

При этом остаются общие для них аргументы:

F = X&

В этом случае:

Z

X

 

Y

минимальная форма имеет вид:

F =

Приложение 2

Системы счисления

Система счисления – совокупность приемов и правил однозначного обозначения чисел с помощью особых символов: 6, 110₂, XI.

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

Количество цифр, составляющих алфавит, называется его размерностью.

Исторически первой системой счисления является односимвольная – использовалась только одна цифра:

•

••

•••

Известны два типа систем счисления:

· непозиционная

· позиционная

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

I 1

V 5

X 10

L 50

C 100

D 500

M 1000

Римская система счисления является аддитивной – число в ней получается как результат сложения и вычитания базовых цифр:

VI 6

IV 4

В этих числах используются две цифры – I и V. Независимо от того, где они стоят в числах, они обозначают цифры 1 и 5, только в первом случае они складываются, а во втором – вычитаются.

Недостатки непозиционных систем счисления:

· большое количество цифр для изображения числа: MCMXCIII – 1993,

· сложность выполнения арифметических операций.

В позиционных системах счисления значение каждой цифры в изображении числа зависит от ее позиции в нем:

354 = 3×100 + 5×10 + 4×1

В этой записи 3, 5 и 4 являются цифрами десятичной системы счисления, а 100, 10 и 1 – их веса в числе.

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

В десятичной системе счисления, известной нам с детства, используется десять цифр, поэтому ее основание S=10:

354 = 3×10² + 5×10¹ + 4×10⁰

Вес цифры в числе можно представить как основание системы счисления в степени, равной номеру разряда числа:

10⁰ вес разряда единиц – номер разряда единиц всегда равен нулю!

10¹ вес разряда десятков,

10² вес разряда сотен, и так далее.

Нумерация разрядов в целых числах идет справа налево, начиная с нуля. Самый правый разряд называется младшим разрядом числа, а самый левый – старшим.

Представим веса разрядов в виде последовательности чисел, начиная с разряда единиц:

1, 10, 100, 1000, 10000,…

Такая последовательность чисел называется базисом системы счисления. В традиционных системах счисления базис образуют члены геометрической прогрессии. В нетрадиционных системах счисления базис может быть другим:

фибоначчиева:

алфавит – цифры 0, 1

базис – последовательность Фибоначчи: 1, 2, 3, 5, 8, 13, 21,…

факториальная:

базис – последовательность факториалов натуральных чисел: 1!, 2!,3!,…

 

Двоичная система счисления

В ней для записи чисел используются только две цифры: 0 и 1.

Таким образом,

алфавит двоичной системы счисления – 0, 1

основание двоичной системы счисления S = 2

базис двоичной системы счисления образуют веса разрядов двоичных чисел – 2⁰, 2¹, 2², 2³, 2⁴, … или

1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024,…

Представим любое двоичное число через его цифры и веса разрядов:

1011₂ = 1×2⁰ + 1×2¹ + 0×2² + 1×2³ = 1 + 2 + 0 + 8 = 11₁₀

Этим же способом любое двоичное число переводится в десятичную систему счисления.

Обратный перевод – из десятичной в двоичную систему счисления – осуществляется последовательным делением десятичного числа на основание двоичной системы счисления 2 и считыванием остатков от деления справа налево:

11/2 = 5, остаток 1

5/2 =2, остаток 1

2/2 =1, остаток 0

1/2 = 0, остаток 1, получаем 1011₂.

 

Восьмеричная система счисления

Алфавит: 0, 1, 2, 3, 4, 5, 6, 7

Основание S = 8

Базис – степени числа 8: 8⁰, 8¹, 8², 8³, … или 1, 8, 64, 512, …

Представим любое восьмеричное число через его цифры и веса разрядов:

3572₈ = 2×8⁰ + 7×8¹ + 5×8² + 3×8³ = 2×1 + 7×8 + 5×64 + 3×512 = 1914₁₀

Этим же способом любое восьмеричное число переводится в десятичную систему счисления.

Обратный перевод – из десятичной в восьмеричную систему счисления – осуществляется последовательным деление десятичного числа на основание восьмеричной системы счисления 8 и считыванием остатков от деления справа налево:

1914/8 = 239 остаток 2

239/8 = 29 остаток 7

29/8 = 3 остаток 5

3/8 = 0 остаток 3, получаем 3572₈.

 

Особый случай перевода – двоично-восьмеричный

Для перевода двоичного числа в восьмеричное необходимо:

1. разбить двоичное число справа налево по три цифры (недостающие слева дополнить нулями):

10011000101₂ = 010 011 000 101₂

2. каждую тройку цифр представить числом в восьмеричной системе счисления:

010 011 000 101₂ = 2305₈

2 3 0 5

Для перевода восьмеричного числа в двоичное необходимо каждую цифру восьмеричного числа представить ее трехразрядным двоичным эквивалентом:

2305₈ = 010 011 000 101₂

2 3 0 5