Характеристическая функция нуля.




МАТЕМАТИЧЕСКАЯ ЛОГИКА

4 семестр

 

Лектор Вагин Вадим Николаевич

 

Москва, 2009/2010

Лекция № 1.

БУЛЕВЫФУНКЦИИ (ФАЛ).

 

Рассмотрим множество .

Фиксированный набор будем обозначать . Их число .

Рассмотрим множество .

 

Определение 1.

Функция, дающая однозначное отображение называется булевой или функцией алгебры логики (ФАЛ).

 

Теорема 1.

Число булевых функций, зависящих от n аргументов, равно .

 

       
       
 
       
       


3

 

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

 

Функции-константы:

Функции одного переменного:

x
     
     

 

 

    конъюнкция дизъюнкция импликация эквивалентность би-импликация сложение по модулю 2 стрелка Пирса штрих Шеффера
                 
                 
                 
                 

 

Определение 2.

Функция F, полученная из множества функций называется суперпозицией этих функций, если она получена с применением двух правил: переименованием аргументов и подстановкой функций вместо аргументов.

 

Выражение одних булевых функций через другие.

 

Утверждение 1.

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

 

               
               
               
               

 

Утверждение 2.

Аналог законов де Моргана.

 

             
             
             
             

 

Свойства.

1. Коммутативность:

НО!

2. Ассоциативность:

НО!

3. Дистрибутивность:

 

Аналитическая запись булевых функций.

 

Рассмотрим фиксированный набор элементов

, .

, .

Рассмотрим функцию

Назовём характеристической функцией единицы.

 

Теорема 2.

– множество наборов аргументов, на которых f принимает значение 1.

 

4 Пусть имеем фиксированный набор , для которого F = 1. Значит, что среди всех существует такая, чей индекс i совпадает с номером набора значений аргумента.

Пусть имеем фиксированный набор , для которого F = 0. Значит, что среди всех нет ни одной, чей индекс i совпадает с номером набора значений аргумента. 3

 

Определение 3.

Введём понятие степени аргумента

 

Рассмотрим конъюнкцию .

Рассмотрим 4 случая:

 

Теорема 3.

Любая ФАЛ кроме константы 0 может быть представлена в виде

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

 

Алгоритм получения СДНФ:

1. Выбираем те наборы, на которых f = 1.

2. Выписываем конъюнктивные наборы, причём

3. Объединяем все конъюнкции дизъюнкциями.

 

Пример.

         
        ü
        ü
         
         
        ü
         
        ü

 

Лекция № 2.

БУЛЕВЫФУНКЦИИ (ФАЛ).

 

Теорема 1.

Любая ФАЛ кроме константы 0 может быть представлена в виде

Такое представление функции называется СПНФ (совершенная полиномиальная нормальная форма).

 

Алгоритм получения СПНФ:

1. Выбираем те наборы, на которых f = 1.

2. Выписываем конъюнктивные наборы, причём

3. Объединяем все конъюнкции логической связкой .

 

Пример.

         
        ü
        ü
         
         
        ü
         
        ü

 

Теорема 2.

Любая ФАЛ кроме константы 1 может быть представлена в виде

Такое представление функции называется СКНФ (совершенная конъюнктивная нормальная форма).

 

4 Возьмём произвольную ФАЛ и представим её в СДНФ:

Применим операцию отрицания к равенству.

3

 

 

Алгоритм получения СКНФ:

1. Выбираем те наборы, на которых f = 0.

2. Выписываем дизъюнктивные наборы, причём

3. Объединяем все наборы конъюнкцией.

 

Пример.

        ü
         
         
        ü
        ü
         
        ü
         

 

Характеристическая функция нуля.

 

     
     
     
     

 

Теорема 3.

Любая ФАЛ кроме константы 1 может быть представлена в виде

Такое представление функции называется САПНФ (совершенная анти полиномиальная нормальная форма).

 

Алгоритм получения САПНФ:

1. Выбираем те наборы, на которых f = 0.

2. Выписываем дизъюнктивные наборы, причём

3. Объединяем все наборы эквивалентностями.

 

Пример.

        ü
         
         
        ü
        ü
         
        ü
         

 

Теорема 4.

Любая ФАЛ кроме константы 1 может быть представлена в виде

Такое представление функции называется СИНФ-1 (совершенная импликативная нормальная форма 1 рода).

 

Алгоритм получения СИНФ-1:

1. Выбираем те наборы, на которых f = 0.

2. Выписываем импликативные наборы, причём

3. Объединяем все наборы конъюнкциями.

 

Пример.

        ü
         
         
        ü
        ü
         
        ü
         

 

Теорема 5.

Любая ФАЛ кроме константы 0 может быть представлена в виде

Такое представление функции называется СИНФ-2 (совершенная импликативная нормальная форма 2 рода).

 

Алгоритм получения СИНФ-2:

1. Выбираем те наборы, на которых f = 1.

2. Выписываем импликативные наборы, причём

3. Объединяем все наборы дизъюнкциями.

 

Пример.

         
        ü
        ü
         
         
        ü
         
        ü

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2019-05-16 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: