Законы и теоремы алгебры логики

Закон тождества. Всякое высказывание тождественно самому себе: А = А

Закон непротиворечия. Высказывание не может быть одновременно истинным и ложным. Если высказывание А — истинно, то его отрицание не А должно быть ложным. Следовательно, логическое произведение высказывания и его отрицания должно быть ложно: A & A = 0

Закон исключенного третьего. Высказывание может быть либо истинным, либо ложным, третьего не дано. Это означает, что результат логического сложения высказывания и его отрицания всегда принимает значение истина: A v A = 1.

Закон двойного отрицания. Если дважды отрицать некоторое высказывание, то в результате мы получим исходное высказывание: A = A

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

Законы Моргана: (A v B)= А & В

(A & B)= А v В

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

Логическое умножение Логическое сложение

A & B = B & A A v B = A v B

Правило ассоциативности. Если в логическом выражении используются только операция логического умножения или только операция логического сложения, то можно пренебрегать скобками или произвольно их расставлять:

Логическое умножение Логическое сложение

(A & B) & C = A & (B & C) (A v B) v C = A v (B v C)

Правило дистрибутивности. В отличие от обычной алгебры, где за скобки можно выносить только общие множители, в алгебре высказываний можно выносить за скобки как общие множители, так и общие слагаемые:

Дистрибутивность умножения Дистрибутивность сложения

относительно умножения относительно сложения

(a x b) + (a x c) = a x (b + c)

(A & B) v (A & C) = A & (B v C) (A v B) & (A v C) = A v (B & C)

Рассмотрим в качестве примера применения законов логики и правил алгебры логики преобразование логического выражения. Пусть нам необходимо упростить логическое выражение:

(А &. В) v (A & В).

Воспользуемся правилом дистрибутивности и вынесем за скобки А:

(А & В) v (А & В) = А & (В v В).

По закону исключенного третьего В v В = 1, следовательно:

А & (В v B) = А &. 1 = А.

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

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

Для начала проведём границу между числом и цифрой.

· Число — это некоторая абстрактная сущность для описания количества (определение из Википедии).

· Цифры — это знаки, используемые для записи чисел.

Цифры бывают разные: самыми распространёнными являются арабские цифры, представляемые известными нам знаками от нуля (0) до девяти (9); менее распространены римские цифры, мы их можем иногда встретить на циферблате часов или в обозначении века (XIX век).

Итак запомним:

· число — это абстрактная мера количества;

· цифра — это знак для записи числа.

Поскольку чисел гораздо больше чем цифр, то для записи числа обычно используется набор (комбинация) цифр.

Только для небольшого количества чисел - для самых малых по величине - бывает достаточно одной цифры.

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

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

Это свойство определяется системой счисления и служит основанием для простейшей классификации таких систем.

Итак, указанное основание позволяет все системы счисления разделить на три класса (группы):

· позиционные;

· непозиционные;

· смешанные.

41. Формы представления чисел в ЭВМ.

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

естественная форма или форма с фиксированной запятой (точкой);

нормальная форма или форма с плавающей запятой (точкой);

Пример:

(естественная форма) 452,34 = 452340*10^-3 = 0,0045234*10⁵ = 0,45234*10³ (нормальная форма)

Всякое десятичное число, прежде чем оно попадает в память компьютера, преобразуется по схеме:

X₁₀ → X₂ = M₁ × [10₂]^r

После этого осуществляется ещё одна важная процедура:

мантисса с её знаком заменяется кодом мантиссы с её знаком;

порядок числа с его знаком заменяется кодом порядка с его знаком.

Указанные коды двоичных чисел - это образы чисел, которые и воспринимают вычислительные устройства. Каждому двоичному числу можно поставить в соответствие несколько видов кодов.

Существуют следующие коды двоичных чисел:

· Прямой код;

· Обратный код;

· Дополнительный код.

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

42. Переключательные функции (ПФ). Алгебра переключательных функций.