Реферат: Булевы функции (лабораторные работы)

Лабораторная работа №1

Булевы функции

Функцией алгебры логики (булевой функцией) <
от переменных
называется функция, принимающая значения 1,0 и аргументы которой также принимают значения 1,0.>

Всякая булева функция от <
переменных может быть задана с помощью таблицы истинности>

<
>

Данная таблица состоит из <
строк, причем в ней все наборы (
) расположены в порядке возрастания их номеров. Следующие булевы функции мы будем называть элементарными.>

<
— константа 0;>

<
— константа 1;>

<
— тождественная функция;>

<
— отрицание
;>

<
— конъюнкция
и
;>

<
— дизъюнкция
и
;>

<
— импликация
и
;>

<
— эквивалентность
и
;>

<
— сложение
и
по
2;>

<
— функция Шеффера;>

<
— функция Пирса.>

Данные функции задаются следующими таблицами истинности

<
>

Приведем определение формулы алгебры логики:

каждая элементарная булева функция — формула;

если некоторое выражение <
есть формула, то
тоже формула;>

если некоторые выражения <
и
есть формулы, то выражения

,

,

,

,
+
,

,

тоже формулы;>

других формул: кроме построенных по п.п.

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

Две формулы <
и
называются равносильными, если они определяют одну и ту же булеву функцию (запись
=
будет означать, что формулы
и
равносильны).>

Приведем перечень важнейших равносильностей (законов) алгебры логики.

1. <
— закон тождества;>

2. <
— закон противоречия;>

3. <
— закон исключения третьего;>

4. <
— закон двойного отрицания;>

5. <
,
— законы идемпотентности;>

6. <
,
>

— законы коммутативности;

7. <
, >

— законы дистрибутивности;

<
>