Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
вопросы к экзамену по ОиФ ЭВМ.doc
Скачиваний:
2
Добавлен:
01.03.2025
Размер:
1 Мб
Скачать
☆
  1. Понятие функций алгебры логики. Способы описания функций алгебры логики.

Определение. Функцией алгебры логики ( логической функцией или булевой функцией ) называется функция, аргументы которой и ее значения могут принимать значения из двухэлементного множества ( обычно из    Е2 = { 0,1 } ).

Любая логическая функция n переменных может быть задана таблицей, в левой части которой перечислены   2   наборов значений переменных; в правой части- значения функции на этих наборах. Наборы переменных располагаются в лекси-кографическом порядке, который совпадает с порядком возрастания наборов, рас-сматриваемых как двоичные числа.

Число различных функций n переменных, обозначается Р2(n). Оно равно Р2(n)=  – числу различных двоичных векторов длины 2 . Рассмотрим табличное за-дание функции одной переменной ( n=1 ). В этом случае различных наборов пере-менной - 2,     0 и 1.  Число различных функций равно  Р2(1) = 22 = 4, а различные векторы длины   2   имеют вид     (0,0),   (0,1),    (1,0),   (1,1).   

Все эти функции представлены в табл. 1.1.

Таблица 1.1

х

f0

f1

f2

f3

0

0

0

1

1

1

0

1

0

1

Эти функции называются и обозначаются следующим образом:

f0(x) = 0 - константа ноль,       f1(x) = x – тождественная функция,

f2(x) =   –отрицание x (читается “ не х“),     f3(x) = 1 –константа единица.

Укажем следующие 4 способа задания функций алгебры логики:

  1. словесное описание;

  2. табличное представление;

  3. графическое изображение;

  4. алгебраическое (в виде формулы).

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

x

y

f(x,y)

0

0

0

– табличное представление.

0

1

1

1

0

1

1

1

0

В графическом изображении единичные значения функции отмечаются некоторым способом, например «*», как на рисунке 1, а нулевые значения представляются неотмеченными вершинами единичного «куба» (в данном случае – квадрата). Та же функция задается формулой:  ^

  1. Характеристика понятий элементарной конъюнкции и элементарной дизъюнкции. Понятия ранга логической функции, минтерма и макстерма.

В логике высказываний элементарной конъюнкцией называется конъюнкция литералов:

, где   — литералы.

В логике высказываний элементарной дизъюнкцией называется дизъюнкция литералов:

, где   — литералы.

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

Всякая булева формула может быть приведена к дизюнктивной нормальной форме вида  , где   — минтерм.

Макстерм — Дизъюнктивный одночлен (макстерм) от переменных дизъюнкция этих переменных или их отрицаний. Макстерм равен 0 только при единственном наборе аргументов. Если макстерм содержит одновременно переменную и её отрицание, то он всегда равен 1.… …