Катаев А.В., ВолгГТУ. Алгебра логики - файл n1.docx

приобрести
Катаев А.В., ВолгГТУ. Алгебра логики
скачать (102.5 kb.)
Доступные файлы (1):
n1.docx103kb.08.07.2012 20:35скачать

n1.docx

Алгебра логики (булева алгебра).


Алгебра логики. Функции алгебры логики. Таблицы истинности. Пропозициональные формулы. Равносильные формулы. Основные тождества алгебры логики. Двойственные функции. Полные системы связок. Конъюнктивные и дизъюнктивные нормальные формы. Совершенные КНФ и ДНФ. Тавтологии. Противоречия. Проблема разрешимости в алгебре логики. Логические следствия. Основные схемы доказательств.

Алгебра логики


Алгебраическая система (алгебра) – пара , где G - это множество элементов (носитель), а M – множество операций, заданных на G (сигнатура).

(n-арная операция на G задаёт отображение на G)

Определение: Алгебраическая система, образованная множеством B = {0,1} вместе со всеми возможными операциями на нем, называется алгеброй логики.

Функцией алгебры логики (или логической функцией) от n переменных называется n-арная операция на В. Эта функция может принимать значения 0 или 1. (т.о. задаёт отображение B^n -> B)

Чаще всего под алгеброй логики понимают алгебру, сигнатура которой включает 3 операции: отрицание, конъюнкцию и дизъюнкцию.

Основные функции алгебры логики:


x1

u1

u2

u3

u4

0

0

0

1

1

1

0

1

0

1

Унарные:

Всего теоретически возможны 4 унарных операции, но лишь одна из них имеет собственное название и обозначение.

u3 - Отрицание: (читается: не-А)

Бинарные:

Всего существует 16 бинарных функций алгебры логики:

x1

x2

b1

b2

b3

b4

b5

b6

b7

b8

b9

b10

b11

b12

b13

b14

b15

b16

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

0

1

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

1

0

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

1

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

b2 - Конъюнкция: (читается А и В)

b8 - Дизъюнкция: (А или В)

b12 - Импликация: (из А следует В)

Результат импликации ложен только тогда, когда исходное (А) высказывание ложно, а результат (B) истинен.

Примеры: (x делится на 4) -> (x делится на 2), Если 2*2 = 5 то 2*2 = 4

b10 - Эквиваленция: , (А равносильно В)

Результат эквиваленции есть истина, если A и B одновременно истины либо ложны (Иными словами, если A=B)

b7 – сложение по модулю или неравнозначность, x1x2

Результат сложения по модулю истинен, если истинно лишь одно из A и B (То есть, если AB)

b9 – cтрелка Пирса x1x2 («или-не»). Результат этой операции равносилен последовательному применению операций дизъюнкции и отрицания

b15 – штрих Шеффера обозначается x1x2, «и-не». Результат этой операции равносилен последовательному применению операций конъюнкции и отрицания. Соответственно, результирующее высказывание будет ложным, только если входящие в него высказывания одновременно истинны. Штрих Шеффера - это операция замечательная тем, что её одной (необходимое количество раз применённой) достаточно, чтобы записать любое сложное высказывание. Является основной операцией в электронике.

Формулы алгебры логики.


Атомарные высказывания обозначаются маленькими буквами и называются пропозициональными (или булевыми) переменными. Формулы алгебры логики называются пропозициональные формулы.

Формулой является строка (знакосочетание), которая является пропозициональной переменной либо совпадает с одной из строк (), , (, (, (, где A и B – формулы.

Для сокращения числа скобок в формуле принято опускать скобки, не влияющие на результат. Например, вместо (x1и(x2иx3)) пишут х1их2их3 (в силу закона коммутативности).

Соглашение о порядке выполнения (приоритете, силе связывания) операций, позволяет отбросить скобки, связывающие разные операции.

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

Соглашение о приоритетах операций позволяет однозначно восстановить пропущенные скобки. Например, …..

Однако, не все скобки могут быть опущены:

A -> (B -> C) А и (B или C)

(Можно тут еще про польскую запись вставить)

Таблицы истинности.


Логическое значение формулы определяется заданными логическими значениями входящих в неё элементарных высказываний.

Пример. x1=1, x2=1, x3=0. Определить значение формулы

Если же ставится задача определить все возможные значения формулы, строится таблица истинности. В этой таблице начальные столбцы соответствуют исходным (элементарным) высказываниям, а последний результирующему (сложному) высказыванию. В начальных столбцах проставляются все возможные комбинации истинности элементарных высказываний, а в последнем истинность сложного высказывания. Каждой комбинации исходных высказываний в формуле соответствует отдельная строка. Число значений формулы (и число строк таблицы) определяется числом n элементарных высказываний и равно 2^n.

x

y

x

y

xy

xy

p

1

1

0

0

0

1

1

1

0

0

1

1

0

0

0

1

1

0

0

1

1

0

0

1

1

0

1

1

Пример.

Для формулы построить таблицу истинности.

В нашем примере 22=4.

Равносильные формулы


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

Обозначение: А=В, читается А равносильно В. Примеры: x=xx, x0=0, xx=1.

Легко видеть, что если А=В, то А=В.

Отношение равносильности обладает следующими свойствами:

1) А=А (рефлексивно)

2) Если А=В, то В=А (симметрично)

3) Если А=В и В=С, то А=С (транзитивно)

Теорема об эквивалентной замене: Если формула A содержит подформулу B, и B = C, то А’=A , где А’ образованна из A заменой B на С.

Основные тождества (равносильные формулы) алгебры логики.





  1. xy=yx; xy=yx – коммутативность

  2. x(yz)= (xy)z; x(yz)= (xy) z; - ассоциативность

  3. x(yz)=(xy)(xz); x(yz)=(xy)(xz) – дистрибутивность

  4. xx=x; xx=x - идемпотентность;

  5. x1=x; x1=1; x0=0; x0=x – законы операций с константами

  6. x(yx)=x; x(yx)=x – законы поглощения;

  7. xx=0 - закон противоречия;

  8. xx=1 - закон исключения третьего

  9. x=x – закон двойного отрицания

  10. xy = yx – закон контрапозиции;

  11. (xy)= xy; (xy)=xy – законы де Моргана;

  12. (xy)(xy)=x; (xy)(xy)=x - формулы расщепления (или склеивания)

Все тождества можно доказать, составив таблицы истинности.

Если в тождестве заменить знак = на <-> то получится тавтология.

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

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

Правило отрицания

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

Правило свертки

xx y=xy

x(xy)=xy

Правило обобщенного склеивания (теорема П.С.Порецкого)

xyyzxz=xyyz

(xy)(yz)(xz)=(xy)(yz)

Преобразование импликации

xy= xy;

 (xy)= xy

Двойственные функции


Функция g(x1,...,xn) = ¬f(¬x1,...,¬xn) называется двойственной функцией к функции f и обозначается f* .

Пример (x & y)* = ¬(¬x & ¬y) = x  y.

Теорема: Функция, двойственная к двойственной функции f равна самой функции f.

Доказательство. f*(x1,...,xn)* = (¬f(¬x1,...,¬xn))* = ¬¬f(¬¬x1,...,¬¬xn) = f(x1,...,xn)

Рассмотрим, что происходит с таблицей двойственной функции. Замена набора (x1,...,xn) на (¬x1,...,¬xn) соответствует ``переворачиванию'' таблицы. Действительно, наборы (x1,...,xn) и (¬x1,..., ¬xn) расположены симметрично относительно середины таблицы. Теперь остаётся применить операцию ¬ к результату функции, т.е. поменять 0 на 1 и 1 на 0. Т.о. вектор значений функции, двойственной к исходной, получается из вектора исходной функции переворачиванием и заменой 0 на 1, а 1 на 0.

Функции x & y и x  y, задаваемые векторами значений (0,0,0,1) и (0,1,1,1) двойственны друг к другу. Также двойственными являются x  y и x  y, задаваемые векторами (0,1,1,0) и (1,0,0,1). Каждая из функций x и ¬x (векторы (0,1) и (1,0) соответственно) двойственна сама себе.

Принцип двойственности.

Функция, двойственная к суперпозиции функций, равна суперпозиции двойственных функций. Точнее:

f0(f1,...,fm)* = f0*(f1*,...,fm*)

Полные системы связок.


Системой связок называется набор базовых функций рассматриваемой алгебры (сигнатура).

Система связок является полной, если любая n-арная булева функция может быть записана в виде пропозициональной формулы с использованием только связок входящих в эту систему.

Система (отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция) является полной.

Система (отрицание, конъюнкция, дизъюнкция) является полной. Именно она и составляет сигнатуру Булевой Алгебры.

Системы связок (отрицание, импликация), (штрих шеффера), (сумма по модулю 2, конъюнкция, 1) так же полны.

Вторая система – только И-НЕ является важной для микроэлектроники.

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

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

  1. монотонные функции;

  2. функции, сохраняющие нуль;

  3. функции, сохраняющие единицу;

  4. линейные функции;

  5. самодвойственные функции.

Если набор содержится в одном из классов, то и все композиции также не выходят за пределы этого класса (легко проверить для каждого из классов в отдельности) и поэтому набор не является полным.

Доказывать обратное не будем, кому интересно, есть, например, тут http://www.intuit.ru/department/calculate/lancalc/1/3.html

Дизъюнктивные и конъюктивные нормальные формы.


Элементарной конъюнкцией называется конъюнкция переменных высказываний и (или) их отрицаний.

Например:

Элементарной дизъюнкцией называется дизъюнкция переменных высказываний и (или) их отрицаний.

Например:

Введём обозначение .

тогда и только тогда, если .

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

  1. тогда и только тогда, если

Элементарная конъюнкция даёт 1 только на наборе переменных, в котором переменные, входящие в неё с отрицанием имеют значение 0, а переменные без отрицания 1.

  1. тогда и только тогда, если

Элементарная дизъюнкция даёт 0 только на наборе переменных, в котором переменные, входящие в неё с отрицанием имеют значение 1, а переменные без отрицания 0)

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

Например, выражение является ДНФ.

Конъюнктивной нормальной формой (КНФ) данной формулы называется равносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций.

Например, выражение – КНФ.

Для того, чтобы построить по данной формуле алгебры логики равносильную ей ДНФ или КНФ необходимо:

  1. Перейти в сигнатуру алгебры логики (выразить все операции через дизъюнкцию, конъюнкцию и отрицание),

  2. Воспользоваться законом де Моргана для того, чтобы отрицания стояли лишь над элементарными переменными высказываниями,

  3. Раскрыть скобки (для построения ДНФ) или воспользоваться дистрибутивным законом (для построения КНФ).


Разложение функций алгебры логики по к переменным.


Теорема. Всякую логическую функцию f(x)=f(x1,x2,x3,…,xn) можно представить в виде

(Знак конъюнкции со списком переменных под ним обозначает, что берётся конъюнкция выражения при всех возможных значениях указанных переменных)

где 1 ? k ? n. Такое представление называется разложением функции по переменным.

Доказательство теоремы основано на том, что выбрав произвольный двоичный набор и подставив его в левую и правую часть мы получим: слева будет f(), а справа

Следствия:

  1. Разложение по k-й переменной:



  1. Разложение по всем переменным:

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

Совершенные нормальные формы.


Совершенная дизъюнктивная нормальная форма.

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

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

Совершенной дизъюнктивной нормальной формой (СДНФ) называется дизъюнктивная нормальная форма, в которой нет одинаковых элементарных конъюнкций и все элементарные конъюнкции правильные и полные.

Совершенная конъюнктивная нормальная форма.

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

Элементарная дизъюнкция называется полной относительно переменных x,y,z ..., если в неё входит каждая из этих переменных не менее одного раза, включая и их вхождение под знаком отрицания.

Совершенной конъюнктивной нормальной формой (СКНФ) относительно переменных x,y,z,... , называется конъюнктивная нормальная форма, в которой нет одинаковых элементарных дизъюнкций и все элементарные дизъюнкции правильные и полные относительно переменных x,y,z,... .

Построения СДНФ и СКНФ.


Построение СДНФ:

1. Преобразование исходной формулы в ДНФ (см выше):

Шаг 1.

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

Шаг 2.

Преобразовать полученную формулу к равносильному ей виду, в котором все конъюнкции выполняются раньше, чем дизъюнкции (раскрыть скобки), т.е. построить ДНФ для исходной формулы.

2.Преобразование ДНФ в СДНФ.

Шаг 3.

Если в ДНФ есть несколько одинаковых элементарных конъюнкций, то оставляем только одну - это преобразование приводит к равносильной формуле , т.к. xVx=x.

Шаг 4.

Делаем все элементарные конъюнкции правильными с помощью следующих двух преобразований:

- если в элементарной конъюнкции переменная входит со своим отрицанием, то удаляем эту конъюнкцию из ДНФ.

- если некоторая переменная входит в элементарную конъюнкцию несколько раз, причем или во всех случаях без отрицаний, или во всех случаях с отрицаниями, то оставляем только одну эту переменную.

Шаг 5.

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

Алгоритм построения СКНФ.

1. Преобразование исходной формулы в КНФ.

Шаг 1.

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

Шаг 2.

Преобразовать полученную формулу к равносильному ей виду, в котором все дизъюнкции выполняются раньше, чем конъюнкции (применить дистрибутивный закон), т.е. построить КНФ для исходной формулы.

2.Преобразование КНФ в СКНФ.

Шаг 3.

Если в КНФ есть несколько одинаковых элементарных дизъюнкций , то оставляем только одну - это преобразование приводит к равносильной формуле ,т.к. x&x=x.

Шаг 4.

Делаем все элементарные дизъюнкции правильными с помощью следующих двух преобразований:

- если в элементарной дизъюнкции переменная входит со своим отрицанием, то удаляем эту дизъюнкцию из КНФ.

- если некоторая переменная входит в элементарную дизъюнкцию несколько раз, причем или во всех случаях без отрицаний, или во всех случаях с отрицаниями, то оставляем только одну эту переменную.

Шаг 5.

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

Построение совершенных нормальных форм с помощью таблиц истинности


Для построения СДНФ или СКНФ, исходя из теоремы о разложении функции алгебры логики от n переменных по k переменным (k=n), можно воспользоваться таблицами истинности.

Для построения СДНФ отметим в таблице истинности те наборы значений переменных, на которых функция равна 1. Для каждого такого набора построим полную правильную элементарную конъюнкцию по следующей схеме: если значение некоторой компоненты равно 1, то соответствующая переменная входит в элементарную конъюнкцию без отрицания, если значение компоненты 0, то соответствующая переменная входит в элементарную конъюнкцию с отрицанием. Объединив, таким образом, построенные правильные полные элементарные конъюнкции знаками дизъюнкции, получим совершенную дизъюнктивную нормальную форму.

Для построения СКНФ отметим в таблице истинности те наборы значений переменных, на которых функция равна 0. Для каждого такого набора построим полную правильную элементарную дизъюнкцию по следующей схеме: если значение некоторой компоненты равно 1, то соответствующая переменная входит в элементарную дизъюнкцию с отрицанием, если значение компоненты 0, то соответствующая переменная входит в элементарную дизъюнкцию без отрицания. Объединив, таким образом, построенные правильные полные элементарные дизъюнкции знаками конъюнкции, получим совершенную конъюнктивную нормальную форму.

Построение совершенных нормальных форм, используя принцип двойственности.


Построение совершенной конъюнктивной нормальной формы.

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

Построение совершенной дизъюнктивной нормальной формы.

Рассмотрим вместо исходной функции её отрицание и построим для полученной формулы алгебры логики её совершенную конъюнктивную нормальную форму. Взяв затем отрицания от левой и правой частей полученного выражения и применив, если это необходимо. закон де Моргана, а так же возможно упростив полученное выражение, получим совершенную дизъюнктивную нормальную форму для исходной функции.

Тавтологии и противоречия. Проблема разрешимости в алгебре логики. Логические следствия.


Формула алгебры логики называется тождественно истиной, общезначимой или тавтологией, если она принимает значение 1 при всех значениях входящих в неё элементарных переменных.

Будем обозначать тавтологию F, где F - тождественно истинная формула, а - обозначение тавтологии.

Примеры тавтологий: xx и x(yx).

Противоречием или тождественно ложной формулой в алгебре логики называют всякую формулу, которая принимает значение 0 при любых значениях входящих в неё элементарных переменных высказываний.

Пример противоречия: xx.

Формула алгебры логики называется выполнимой, если она принимает одно значение 1 хотя бы на одном наборе значений входящих в неё элементарных переменных высказываний.

Любая формула, не являющаяся противоречием, является выполнимой (и наоборот).

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

Очевидно, что эта проблема может быть решена путём построения для заданной формулы таблицы истинности. Однако, существует более эффективный способ решения этой проблемы.

Теорема о тождественной истинности формулы алгебры логики.

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

Доказательство.

Пусть каждая элементарная дизъюнкция КНФ, равносильной исходной формуле, содержит некоторую переменную вместе с её отрицанием. Рассмотрим произвольную элементарную дизъюнкцию и пусть в ней содержится некоторая переменная x и её отрицание , тогда, из-за того, что xV=1, эта элементарная конъюнкция будет равна 1. Так для всех элементарных конъюнкций КНФ.

Пусть исходная формула является тождественно истиной. Рассмотрим КНФ ей равносильную и предположим, что в некоторой элементарной дизъюнкции этой КНФ нет пары типа x и . Тогда рассмотрим набор из 0 и 1, такой, что в этом наборе компонента равна 1, если в рассматриваемой элементарной дизъюнкции ей соответствующая переменная входит под знаком отрицания и равна 0, если соответствующая переменная входит без знака отрицания. Тогда на этом наборе элементарная дизъюнкция будет равна 0, тем самым и значение КНФ на этом наборе будет равно 0, что противоречит тожественной истинности исходной формулы.

Теорема о тождественной ложности формулы алгебры логики

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

Доказательство аналогично доказательству предыдущей теоремы.

Формула алгебры логики f называется логическим следствием формул f1,f2,…,fm, если для любых наборов значений переменных, входящих в формулы, f1,f2,…,fm , f для которых истины все формулы f1,f2,…,fm, формула f тоже истина. Обозначение f1,f2,…,fmf.

Теорема о логическом следствии

Формула алгебры логики f является логическим следствием формулы алгебры логики g, тогда и только тогда, если gf.

Доказательство.

Пусть n - количество различных переменныхf, входящих в формулы g и f, и а n - мерный двоичный набор из 0 и 1.

Пусть gf , покажем что.

Так как f является следствием из g, то на любом наборе а, если g(а)=1, то f(а)=1. Если же g(а)=0, то 0f принимает значение 1 при любом значенииf (а).

Пусть gf, покажем, что gf.

f- следствие из g, если при любом наборе а, из g(а)=1 следует f(а)=1.

Пусть а, такой набор, что g(а)=1, тогда из того, что gf- тождественно истинная формула, её значение на наборе а должно равняться 1, а это для операции импликации может быть лишь тогда, когда f (а)=1.

Теорема доказана.

Аналогичным образом доказывается и более общая теорема.

Обобщённая теорема о логическом следствии

f1,f2,…,fm f тогда и только тогда, если f1f2...fm f

Множество формул алгебры логики { f1,f2,…,fm } называется непротиворечивым, если существует по крайней мере один такой набор значений переменных, входящих в эти формулы, что все формулы из множества на этом наборе равны 1.

Множество формул алгебры логики { f1,f2,…,fm } называется противоречивым, если при всяком наборе значений переменных, входящих в эти формулы, по крайней мере одна из формул принимает значение 0.

Отсюда, {} - непротиворечиво, если f1f2...fm =1 по крайней мере на одном наборе и противоречиво, если f1f2...fm =0 для любого набора значений переменных.

Теорема о противоречивости множества формул алгебры логики

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

Для доказательства теоремы используется теорема 4 и определение операции импликации.

Теорема о тождественной истинности формулы алгебры логики

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

Основные схемы доказательств

Схема 1. «Если x то y»

Доказательство теорем типа “если x, то y”.

Схема доказательства основана на следующем логическом следствии:

.

Действительно, по теореме 5 из следует



Схема 2. «доказательство от противного» или метод косвенного доказательства.

Схема доказательства основана на следующем логическом следствии:



Действительно, по теореме 6 из следует, что



Схема 3 «доказательство построением цепочки импликаций»

Схема доказательства основана на следующем логическом следствии:



Действительно, по теореме 6 из следует, что



Схема 4. «Доказательство разбором случаев»

Схема доказательства основана на следующем логическом следствии:

.

Действительно, по теореме 6 из следует, что



Контрольные вопросы:

  1. Дайте определение логической функции. Какие значения она может принимать?

  2. Как определить значение логического выражения, если известны значения переменных?

  3. Что такое таблица истинности? Каков порядок ее построения?

  4. Сколько столбцов будет содержать таблица истинности для функции четырех переменных?

  5. В каких случаях формулы xy, xy, xy имеют значение 1.

  6. Каков порядок выполнения логических операций?

  7. Какими свойствами обладает отношение равносильности?

  8. Каким способом можно привести функцию к ДНФ?

  9. Дайте определение СДНФ.

  10. Опишите алгоритм приведения ДНФ к СДНФ.

  11. Перечислите основные схемы доказательств.


Алгебра логики (булева алгебра)
Учебный материал
© nashaucheba.ru
При копировании укажите ссылку.
обратиться к администрации