Главная страница
Навигация по странице:

  • Лекция 4. Булевы функции.

  • Элементарные булевы функции. Равносильности

  • Основные равносильности Закон двойного отрицания

  • , .

  • Дополнительные равносильности


    		•

    Дискретная математика (1). Лекция Составные высказывания


    Скачать 2.15 Mb.
    НазваниеЛекция Составные высказывания
    Дата05.09.2022
    Размер2.15 Mb.
    Формат файлаdoc
    Имя файлаДискретная математика (1).doc
    ТипЛекция
    #662788
    страница4 из 16
    1   2   3   4   5   6   7   8   9   ...   16

    Логическое следствие


    Определение. Формула B есть логическое следствие формул A1, A2, .., An, если формула B принимает истинное значение при тех же значениях, при которых истинна каждая из формул A1, A2, .., An.

    Запись (A1, A2, .., An)B означает, что B – логическое следствие формул A1, A2, .., An.

    Пример. (AB, A ) .

    Докажем данное следствие.

    A
    B
    AB


    A



    И
    И
    И
    Л
    Л
    Л

    И
    Л
    Л
    И
    И
    Л

    Л
    И
    И
    Л
    И
    И

    Л
    Л
    И
    И
    И
    И

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

    Определение. Формулы F и G называются равносильными, если они являются логическими следствиями друг друга. Обозначение: .

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

    Следующие теоремы связывают логическое следствие и импликацию, равносильность и эквиваленцию.

    Теорема1. тогда и только тогда, когда AB – тавтология.

    Теорема2. тогда и только тогда, когда AB – тавтология.

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

    Булевы функции F от n переменных могут быть заданы посредством таблицы истинности, содержащей строк и столбцов. В левой части таблицы содержатся наборы значений n переменных, расположенные в порядке возрастания их десятичного эквивалента, а в правой ее части  значения функции F на соответствующих наборах значений переменных.

    В качестве примера рассмотрим таблицу истинности некоторой булевой функции F, зависящей от переменных , и .




    F

    0
    0
    0
    0

    0
    0
    1
    0

    0
    1
    0
    1

    0
    1
    1
    0

    1
    0
    0
    0

    1
    0
    1
    1

    1
    1
    0
    1

    1
    1
    1
    1

    Булева функция n переменных F однозначно определяется - разрядным булевым вектором ее значений w(F) (т.е. w(F)  таблица истинности функции F). Например, в этом примере имеем w(F)=(00100111).

    Рассматриваемая булева функция F принимает значения 0 на наборах 000, 001, 011 и 100, а значение 1  на наборах 010, 101, 110 и 111.

    Множество наборов, на которых функция F принимает значение 1, называется характеристическим и обозначается через NF. В настоящем примере имеет место NF = (010, 101, 110, 111).

    Общее число различных булевых функций F от n переменных равно . Т.е. число булевых функций от двух переменных равно , от трех переменных .

    Элементарные булевы функции. Равносильности

    Булевых (или логических) функций от одной переменной . Они приведены в следующей таблице:
    0


    отрицание
    1

    0
    0
    0
    1
    1

    1
    0
    1
    0
    1


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


    конъюнк-

    ция
    дизъюнк-

    ция
    имплика-

    ция

    эквивален-тность

    сложение по модулю два

    стрелка

    Пирса

    штрих

    Шеффера

    0
    0
    0
    0
    1
    1
    0
    1
    1

    0
    1
    0
    1
    1
    0
    1
    0
    1

    1
    0
    0
    1
    0
    0
    1
    0
    1

    1
    1
    1
    1
    1
    1
    0
    0
    0

    Функция называется конъюнкцией, ее обозначают также , но чаще всего знак конъюнкции аналогично знаку умножения опускают и пишут . Конъюнкция равна единице, только если =1 и =1 одновременно, поэтому ее часто называют функцией И. Еще одно название конъюнкции ― логическое умножение, поскольку ее таблица истинности действительно совпадает с таблицей обычного умножения для чисел 0 и 1.

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

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

    Если формула a реализует булеву функцию F,которая тождественно равна единице, то она называется тождественно истинной. Если формула a реализует булеву функцию F, которая тождественно равна нулю, то она называется тождественно ложной.

    Если формулы a и b зависят от одних и тех же переменных и реализуют одну и ту же булеву функцию F,то формулы a и b называются равносильными.

    Основные равносильности

    Закон двойного отрицания

    .

    Идемпотентность

    , .

    Коммутативность

    , .

    Ассоциативность

    , .

    Дистрибутивность

    , .

    Законы де Моргана

    , .

    Формулы с константами

    , , ,

    , , .

    Дополнительные равносильности

    ,

    ,

    ,

    ,

    ,

    ,

    ,

    ,

    , (законы склеивания),

    (закон поглощения).

    (закон обобщенного склеивания).

    Переменная булевой функции F называется несущественной (или фиктивной), если , то есть если изменение значения в каждом наборе значений не меняет значения функции. При этом существует такая формула, реализующая эту булеву функцию, в которой отсутствует .
    1   2   3   4   5   6   7   8   9   ...   16

    написать администратору сайта