Основные понятия алгебры логики. Элементарные функции алгебры логики. Свойства функций конъюнкции, дизъюнкции, отрицания

Страницы работы

14 страниц (Word-файл)

Фрагмент текста работы

2   ОСНОВНЫЕ ПОНЯТИЯ АЛГЕБРЫ ЛОГИКИ

2.1 Элементарные функции алгебры логики

Основное понятие алгебры логики – высказывание. Высказывание – некоторое предложение, о котором можно утверждать, что оно истинно или ложно. Например, высказывание «Земля – это планета Солнечной системы» истинно, а о высказывании «на улице идет дождь» можно сказать , истинно оно или ложно, если указаны дополнительные сведения о погоде в данный момент.

Любое высказывание можно обозначить символом x и считать, что x=1, если высказывание истинно, а x=0 – если высказывание ложно.

Логическая (булева ) переменная – такая величина x, которая может принимать только два значения :  x={0,1}.

Высказывание абсолютно истинно, если соответствующая ему логическая величина принимает значение x=1 при любых  условиях. Высказывание абсолютно ложно, если соответствующая ему логическая величина принимает значение x=0 при любых  условиях.  Например, высказывание «Земля – спутник Марса» абсолютно ложно.

Логическая функция ( функция алгебры логики ) – функция  f( x1, x2, … , xn), принимающая значение, равное нулю или единице на наборе логических переменных  x1, x2, … , xn.

Логические функции одной переменной представлены в таблице 2.1.

Таблица 2.1

x

f1(x)

абсолютная истина

f2(x)

абсолютная ложь

f3(x)

тождественная функция

f3(x)ºx

f4(x)

отрицание

f4(x)=Øx=

0

1

0

0

1

1

1

0

1

0

Логические функции двух переменных представлены в таблице  2.2.

Таблица 2.2

функция

x1x2

Примечание

00

01

10

11

f0

0

0

0

0

абсолютная ложь

f1

0

0

0

1

конъюнкция  или 

f2

0

0

1

0

запрет x2  ()

f3

0

0

1

1

f3ºx1

f4

0

1

0

0

запрет x1  ()

f5

0

1

0

1

f5ºx2 

f6

0

1

1

0

сложение по модулю 2 ( исключающее или )

f7

0

1

1

1

дизъюнкция    или 

f8

1

0

0

0

функция Пирса  

f9

1

0

0

1

равнозначность    x1ºx2

f10

1

0

1

0

f11

1

0

1

1

импликация

f12

1

1

0

0

f13

1

1

0

1

импликация 

f14

1

1

1

0

функция Шеффера  

f15

1

1

1

1

абсолютная истина

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

f1( x1, x2, … , xn)= f2( x1, x2, … , xn) .

Логические переменные могут быть действительными или фиктивными. Переменная xi действительная, если значение функции f( x1, … , xi, … , xn) изменяется при изменении xi . Переменная фиктивна, если значение функции f( x1, … , xi, … , xn) не изменяется при изменении xi .

Например, функция f( x1, x2, x3) =  , значения которой приведены в таблице 2.3.

Таблица 2.3

x1

0

0

0

0

1

1

1

1

x2

0

0

1

1

0

0

1

1

x3

0

1

0

1

0

1

0

1

f( x1, x2, x3)

0

0

1

1

1

1

1

1

Из таблицы видно, что f( x1, x2, 0) = f( x1, x2, 1) для всех наборов x1 и x2 . Следовательно, x3 – фиктивная переменная.

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

Впервые теория логических функций была применена П.С. Эренфестом к анализу контактных цепей (1910г.) . Возможность описания переключательных схем с помощью логических формул оказалась весьма ценной по двум причинам. Во-первых, с помощью формул удобнее проверять работу схем.  Во – вторых, задание условий работы любой переключательной схемы в виде формул упрощает процесс построения самой переключательной схемы, так как оказалось, что существует ряд эквивалентных преобразований, в результате которых логические формулы упрощаются. При описании переключательных схем замкнутое состояние контакта принимается за истинное высказывание, а разомкнутое – за ложное, поэтому последовательное соединение контактов можно рассматривать как функцию И ( конъюнкцию ), а параллельное -  как функцию ИЛИ ( дизъюнкцию ). Использование логических функций оказалось особенно полезным для описания работы логических элементов ЭВМ.

2.2 Свойства  функций конъюнкции, дизъюнкции, отрицания

Для конъюнкции, дизъюнкции и отрицания справедливы следующие восемь равенств. Пусть x – некоторая логическая переменная, тогда

1.  , что означает возможность замены в логическом выражении всех двойных отрицаний на исходные величины;

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

3.  ;

4.  ;

5.  ;

6.  ;

7.  ;

8.  .

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

9.  , и   -  ассоциативность;

10.  , и      -   коммутативность;

11.   , и   - дистрибутивность.

Можно доказать справедливость указанных свойств, сравнив таблицы истинности функций из левой и правой частей каждого равенства. Например, для последнего свойства, если обозначить F1= и  F2=, значения этих функций приведены в таблице 2.4

Таблица 2.4

x1

0

0

0

0

1

1

1

1

x2

0

0

1

1

0

0

1

1

x3

0

1

0

1

0

1

0

1

0

0

0

1

0

0

0

1

F1=

0

0

0

1

1

1

1

1

0

0

1

1

1

1

1

1

0

1

0

1

1

1

1

1

F2=

0

0

0

1

1

1

1

1

Хорошо видно, что все значения F1 и F2 совпали на одних и тех же наборах значений переменных  x1, x2, x3 .

Аналогично можно доказать и другие свойства.

12.   , и    - законы де Моргана;

13.   , и  = x1  -  законы поглощения;

14.    -   свойство “склеивания”.

Законы де Моргана справедливы для любого количества переменных :

,

  .

В таблице 2.5 доказана справедливость свойства “склеивания” .

Таблица 2.5

x1

x2

0

0

0

0

0

0

1

0

0

0

1

0

0

1

1

1

1

1

0

1

2.3 Свойства функции сложения по модулю 2

Справедливы следующие свойства :

1.   ;

2.   ;

3.   ;

4.   ;

5.     -   коммутативность;

6.    - ассоциативность;

7.    - дистрибутивность.

Конъюнкцию, дизъюнкцию, отрицание  можно выразить через сложение

Похожие материалы

Информация о работе