Комплект практических работ по предмету «Элементы математической логики».

Комплект практических работ  по предмету

"Элементы математической логики"

Составитель: преподаватель математики Сипачева О.И.

Мурманск

2013 г

Пояснительная записка.

Комплект практических работ по дисциплине "Элементы математической логики " предназначен для студентов колледжа, обучающихся по специальности:  230115 «Программирование в компьютерных системах». Включенные в практические работы задачи стимулируют исследовательскую и творческую деятельность, развивает познавательные интересы, помогают не только глубже понять математику, но и научиться применять полученные знания на практике. Комплект практических работ по данной учебной дисциплине  составлен в соответствии с Государственными требованиями по изучаемому предмету и может быть рекомендован для преподавания дисциплины в ГБОУ СПО «МКЭИТ» и других профильных учебных заведениях, для опубликования в специализированных изданиях. Каждая практическая работа содержат план занятия, краткие теоретические сведения, вопросы для самопроверки по теоретической части материала, образцы решения задач, задания для самостоятельного выполнения, список источников. Время выполнения каждой работы  4 академических часа.

Введение.

  Содержание практических работ позволяет освоить практические приемы составления  таблиц истинности для формул алгебры логики, практические приемы выполнения равносильных преобразований формул алгебры логики и логики предикатов,  научиться  решать логические задачи методами алгебры логики,  решать задачи на РКС (релейно-контактные схемы), применять средства языка логики предикатов для записи и анализа математических предложений,  проводить доказательные рассуждения в ходе решения задач;  применять математические методы для решения профессиональных задач; овладеть техникой равносильных преобразований логических формул,  методами распознавания тождественно истинных формул и равносильных формул,  навыками решения основных задач математической логики и методами их решения.

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

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

Основная часть.

1.1.Список практических работ.

1.2.Ход работы:

1. Познакомиться с теоретическим материалом

2. Сделать краткий конспект теоретического материала в рабочих тетрадях (основные понятия, определения, формулы, примеры).

3. Ответить на контрольные вопросы.

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

5. Защита практической работы.

1.3 Критерии оценивания практических работ

      За полностью выполненную практическую работу ставится «зачет». Если какие-либо задания не выполнены или выполнены неверно, то студент получает от преподавателя указания для выполнения этого задания.

1.4  Практические работы.

  Практическая  работа1.

по предмету «Элементы математической логики»

Преподаватель Сипачева О.И.

Тема: Составление таблиц истинности.  Равносильные преобразования. Упрощение формул логики.

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

Ход работы.

Повторить   краткие теоретические сведения и разобрать задачи с решениями. .

1.1. Высказывания и операции над ними

Математическая логика – это раздел математики, посвященный анализу методов рассуждений, при этом в первую очередь исследуются формы рассуждений, а не их содержание, т.е. исследуется формализация рассуждений? Это разновидность формальной логики, т.е. науки, которая изучает умозаключения с точки зрения их формального строения.

Основное неопределяемое понятие математической логики это высказывание. Под высказыванием понимают предложение, которое может принимать только два значения «истина» или «ложь». Обозначаются высказывания малыми латинскими буквами: a, b, ,…,х,…. или большими латинскими буквами A, B, C…

        В математической логике не рассматривается смысл высказываний, определяется только их логическое значение – «истина» или «ложь». Известному немецкому математику и логику Эрнесту Шредеру пришло в голову предложить в качестве знака для обозначения ложного суждения цифру 0, что, конечно, привело к обозначению истины цифрой 1.

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

       Предикат – логическая функция от п переменных, которая принимает значения истинности или ложности.

Исчисление предикатов – раздел математической логики, объектом которого является дальнейшее изучение и обобщение исчисления высказываний.

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

Примеры.

1. «Река Кола впадает в Кольский залив» – высказывание (истинное).
2. «Число32 кратно 3» – высказывание (ложное).
3. «Может быть, сегодня пойдет снег» – не высказывание.
4. «5х – 9 = 7» – не высказывание (неопределенное высказывание или высказывательная форма).

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

Основные логические операции  над высказываниями.

Отрицанием высказывания х называется высказывание, которое истинно тогда и только тогда, когда высказывание х ложно. Отрицание обозначается  или  х (читается: «не х»).

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

Конъюнкцией двух высказываний х и y называется высказывание, истинное тогда и только тогда, когда истинны оба высказывания х и y. Конъюнкция обозначается: х Ù y,  или х & y (читается: «х и y»). Таблица истинности для х Ù y имеет вид:

Дизъюнкцией двух высказываний х и y называется высказывание, ложное тогда и только тогда, когда оба высказывания х и y ложны. Дизъюнкция обозначается х Ú y (или x+y) (читается: «х или y»). Таблица истинности для х Ú y имеет вид:

Импликацией двух высказываний х и y называется высказывание, ложное тогда и только тогда, когда высказывание х истинно, а y – ложно. Импликация обозначается: х  y (читается: «х влечет y» или «из х следует y»). Высказывание х называется посылкой импликации, а высказывание y – следствием. Таблица истинности для х  y имеет вид:

Эквиваленцией (эквивалентностью) двух высказываний х и y называется высказывание, истинное тогда и только тогда, когда истинности высказываний х и y совпадают. Эквиваленция обозначается: х  y, или х ~ y (читается: «х эквивалентно y» или «х тогда и только тогда, когда y»). Таблица истинности для х  y имеет вид:

1.2. Алгебра Буля.

 Множество высказываний с введенными для них логическими операциями дизъюнкции, конъюнкции и отрицания основными законами этих действий называется алгеброй Буля. Алгебра Буля— исторически первый раздел математической логики, разработанный ирландским логиком и математиком Дж. Булем (George Boole  (1815—1864) — английский математик и логик. Профессор математики Королевского колледжа Корка ). в середине XIX в. Буль применил алгебраические методы для решения логических задач и сформулировал на языке алгебры некоторые фундаментальные законы мышления

Законы алгебры Буля.

Коммутативные законы:

1. x  y º y  x;
2. x  y º y  x;

Ассоциативные законы:

1. x  (y  z) º (x  y)  z;
2. x  (y  z) º (x  y)  z;

Дистрибутивные законы:

1. x  (y  z) º (x  y)  (x  z);
2. x  (y  z) º (x  y)  (x  z);

Идемпотентные законы:

1. x  x º x;
2. x Ú x  º x;

Законы логического сложения и умножения с 0 и 1:

1. x  0 º 0;
2. x Ú 0 º x;
3. x  1 º x;
4. x Ú 1 º 1;

Законы операции «черта»:

1.  º x;
2.  x Ú 0 º x;
3. x Ú 1 º 1;
4.  x º 0;
5. Ú x º 1;

Законы Де Моргана ( Augustus de Morgan (1806- 1871) — шотландский математик и логик; профессор математики в Университетском колледже Лондона):

1. ;
2. .

    Сложением по модулю два (альтернативной дизъюнкцией, логи́ческим сложе́нием, исключа́ющим «ИЛИ», строгой дизъюнкцией) двух высказываний х и y называется высказывание, истинное  тогда и только тогда, когда оба высказывания х и yпринимают разные значения. Дизъюнкция обозначается х  y  (читается: «или х, или y»). Таблица истинности для х  y имеет вид:

      Стрелка Пирса – это отрицание дизъюнкции.

 Стрелка Пирса обозначается X ↓ Y. Читается «ни X, ни Y».

Введена в рассмотрение Чарльзом Пирсом (Сharles Peirce) в 1880—1881 г.г. Таблица истинности для стрелки Пирса имеет вид:

Штрих Шеффера – это отрицание конъюнкции.

Введена в рассмотрение Генри Шеффером в 1913 г. (в отдельных источниках именуется как Пунктир Чулкова)

Штрих Шеффера обозначается x|y , задаётся следующей таблицей истинности:

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

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

Если в формулу алгебры логики вместо переменных x, y,… подставить конкретные высказывания, то получится высказывание, имеющее логическое значение «1» или «0».

Пример.

Высказывание x: «Волга впадает в Каспийское море» – истинное (x = 1),

высказывание y: «Число 16 кратно 3» – ложное (y = 0),

тогда формула А = x Ú y будет иметь логическое значение «1»: А = 1 (см. таблицу истинности для х Ú y).

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

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

Равносильность логических формул можно установить при помощи их таблиц истинности.

Пример. С помощью таблиц истинности проверить, являются ли равносильными формулы  и .

Решение.        Составим таблицы истинности для каждой из формул А и В.

Ответ: данные формулы являются равносильными.

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

2. Выражения одних логических операций через другие:

        12)  x  y º Ú y;                        13)  ;

        14)  x  y º (x  y)  (y  x);                15)  .

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

Пример. Упростить логическую формулу: .

Решение. Используем основные равносильности.

.

Ответ:  x  y.

Образец решения примера.

3.Являются ли эквивалентными следующие высказывания:

Решение.

Составим таблицы истинности для каждого высказывания.

Значения x иy в пятом и восьмом столбцах не совпадают.

Вывод: данные высказывания не являются эквивалентными

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

1. Что понимают в математической логике под высказыванием?
2. Какие действия выполняются над высказываниями?
3. Что называют алгеброй Буля?
4. Законы алгебры Буля.

Для закрепления теоретического материала и получения прочных  знаний решить примеры.

1в.

1.Укажите, в каких случаях высказывание истинно, а в каких ложно:

2.Являются ли эквивалентными следующие высказывания:

   и  

3.Решить булево уравнение:

     2в.

1.Укажите, в каких случаях высказывание истинно, а в каких ложно:

2.Являются ли эквивалентными следующие высказывания:

   и

3.Решить булево уравнение:

    3в 

1.Укажите, в каких случаях высказывание истинно, а в каких ложно:

2.Являются ли эквивалентными следующие высказывания:

 и

3.Решить булево уравнение:

    4в. 

1.Укажите, в каких случаях высказывание истинно, а в каких ложно:

2.Являются ли эквивалентными следующие высказывания:

   и

3.Решить булево уравнение:

5в

1. Укажите, в каких случаях высказывание истинно, а в каких ложно:

2.Являются ли эквивалентными следующие высказывания:

3.Решить булево уравнение:

6в

1. Укажите, в каких случаях высказывание истинно, а в каких ложно:

2.Являются ли эквивалентными следующие высказывания:

3.Решить булево уравнение:

    7в. 

1.Укажите, в каких случаях высказывание истинно, а в каких ложно:

2.Являются ли эквивалентными следующие высказывания:

 и

3.Решить булево уравнение:

         8в. 

1.Укажите, в каких случаях высказывание истинно, а в каких ложно:

2.Являются ли эквивалентными следующие высказывания:

3.Решить булево уравнение:

     9в 

1.Укажите, в каких случаях высказывание истинно, а в каких ложно:

2.Являются ли эквивалентными следующие высказывания:

 и  

3.Решить булево уравнение:

=1

   10в. 

1.Укажите, в каких случаях высказывание истинно, а в каких ложно:

2.Являются ли эквивалентными следующие высказывания:

3.Решить булево уравнение:

=0

     11в. 

1.Укажите, в каких случаях высказывание истинно, а в каких ложно:

2.Являются ли эквивалентными следующие высказывания:

 и

3.Решить булево уравнение:

=0

12в.

1. Укажите, в каких случаях высказывание истинно, а в каких ложно:

2.Являются ли эквивалентными следующие высказывания:

3.Решить булево уравнение:

13в.

1.Укажите, в каких случаях высказывание истинно, а в каких ложно:

2.Являются ли эквивалентными следующие высказывания:

3.Решить булево уравнение:

      14в 

1.Укажите, в каких случаях высказывание истинно, а в каких ложно:

2.Являются ли эквивалентными следующие высказывания:

3.Решить булево уравнение:

15в 

1.Укажите, в каких случаях высказывание истинно, а в каких ложно:

2.Являются ли эквивалентными следующие высказывания:

3.Решить булево уравнение:

  Практическая  работа 2

по предмету по предмету «Элементы математической логики»

Преподаватель Сипачева О.И.

Тема: Приведение формул к совершенным нормальным формам по таблицам истинности.

Цель работы: знать, что такое ДНФ и КНФ, уметь приводить формулы алгебры логики к

  СДНФ и СКНФ и минимизировать их с помощью законов алгебры логики.

Ход работы.

Повторить   краткие теоретические сведения и разобрать задачи с решениями. 

ТОЖДЕСТВЕННО-ИСТИННЫЕ И ТОЖДЕСТВЕННО-ЛОЖНЫЕ ФОРМУЛЫ.

Определение. Формула называется тождественно-истинной (тавто-логией), если для любых наборов переменных она принимает значение И.

Определение. Формула называется тождественно тождественно-ложной, если для любых наборов переменных она принимает значение Л.

В алгебре высказываний используют две нормальные формы: дизъюнктивную  и конъюнктивную нормальные формы формулы (ДНФ и КНФ).

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

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

Каждая формула, не равная тождественно Л, может быть приведена СДНФ, которая является единственной с точностью до перестановки дизъюнктивных членов.

Каждая формула, не равная тождественно И, может быть приведена к СКНФ, которая является единственной с точностью до перестановки конъюнктивных членов.

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

1. Каждое логическое слагаемое формулы содержит все высказывания, входящие в формулу.

2. Все логические слагаемые формулы различны

3. Ни одно логическое слагаемое не содержит высказывание и его отрицание

4. Ни одно логическое слагаемое формулы не содержит одно и то же высказывание дважды.

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

1)Отметить те строки , в последнем столбце которых стоят 0:

2)Выписать для каждой отмеченной строки дизъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке =0, то в дизъюнкцию включают саму эту переменную, если =1, то ее отрицание:

3)Все полученные дизъюнкции связать в конъюнкцию.

1. Образцы  решения

Построить таблицу истинности  для высказывания: , построить СНДФ, СКНФ, найти минимальную ДНФ.

 Решение.

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

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

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

1)Отметить те строки , в последнем столбце которых стоят 1:

2)Выписать для каждой отмеченной строки конъюнкцию всех переменных следующим образом: если значение некоторой переменной в данной строке =1, то в конъюнкцию включают саму эту переменную, если =0, то ее отрицание:

3)Все полученные конъюнкции связать в дизъюнкцию:

Выбираем в таблице строки, в которых булева функция принимает значение 1. В данном случае – это 2-ая, 3-ая, 4-ая, 6-ая и 7-ая строки.

Для каждой строки составляем конъюнкцию: если значение переменной равно 0. то берем ее отрицание, а  если  1, то берем саму переменную. Затем  составляем дизъюнкцию полученных конъюнкций:

.

Выбираем в таблице строки, в которых булева функция принимает значение 0. В данном случае – это 1-ая, 5-ая,  и 8-ая строки:

ДНФ называется минимальной, если она содержит наименьшее число букв  среди всех ДНФ ей равносильных.

Метод Квайна основывается на применении двух основных соотношений.

Соотношение склеивания :

;    

 Соотношение поглощения:

Используя соотношение склеивания получаем:

=,

=. Отсюда,

=()()- сокращенная ДНФ.

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

1. Что такое ДНФ?

1. Чем отличается ДНФ от СДНФ?

1. Как составить ДНФ по таблице истинности?

3) Для закрепления теоретического материала и получения прочных  знаний решить примеры.

Построить таблицу истинности, найти СНДФ, найти минимальную ДНФ.

 для высказывания:

     1в.

1.

2.  

3.  

     2в.

 1.

2.

3.

    3в 

1.

2.

3.

    4в. 

1.    

2  

3  

Построить таблицу истинности, найти СНДФ, найти минимальную ДНФ.

 для высказывания:

5в

1

2.

3.

6в

1     

2.  

3.

    7в. 

1.

2.  

3.

         8в. 

1.

2.  

3.

    9в 

1 .

2.

3.

    10в. 

1.

2.

3.

Построить таблицу истинности, найти СНДФ, найти минимальную ДНФ.

 для высказывания:

     11в.

1 .

2.

3.

12в.

1.

2.

3.

13в.

1.

2.

3.

      14в 

1.

2.

3.

15в 

1  

2.  

3.  

Практическая  работа 3

по предмету по предмету «Элементы математической логики»

Преподаватель Сипачева О.И.

Тема: Решение логических задач.

Цель работы: уметь решать задачи, используя формул алгебры логики.

Ход работы.

Разобрать задачи с решениями. 

• Равносильны ли высказывания:

1. и

            2.  и

            3.  и

• Исходя из разговорной практики, мы знаем, что, имея высказывания А и В,

можно  построить высказывания: не А (неверно, что А); А и В; А или В; если А, то В (из А следует В); А только и только тогда, когда В  (А эквивалентно В, А тождественно В)

Эти высказывания, в отличие от элементарных, естественно назвать сложными, поскольку они уже наделены структурой. Однако они так же, как и простые, могут принимать только два возможных значения: И либо Л.

 Среди следующих высказываний укажите составные; выделите в них простые, обозначив каждое из  них буквой; запишите с помощью логических операций каждое составное высказывание:

1. «Пришла весна, и грачи прилетели».

Решение задачи:

Обозначим через A-«пришла весна»; а через B- «грачи прилетели». Тогда высказывание  

С -«Пришла весна, и грачи прилетели» запишем так:  С= АB.

Ответ: :  С= АB.

2. «Число 6 делится на 2 и число 6 делится на 3».

3. « Неверно, что 4 делится на 3». Обозначим через  простое высказывание «4 делится на 3». Представьте первое высказывание в виде логической формулы.

4.Неверно, что Солнце движется вокруг Земли.

5.Земля имеет форму шара.

6.На уроке математики старшеклассники отвечали на вопросы учителя и писали самостоятельную работу.

7.Если сумма цифр числа делится на 3, то число делится  на  3.

8.Число  делится на 3 тогда и только тогда, когда сумма цифр числа  делится на 3.

9. Число  376 четное и трехзначное.

10. 1) «Летом я поеду в деревню или в туристическую поездку».

     2) «Летом я поеду в деревню или в туристическую поездку, или в санаторий»

     3)   «Если летом я поеду в деревню, то я не поеду в  туристическую поездку»

     4) «Если  летом я не поеду в деревню или в санаторий, то я  поеду в  туристическую поездку».

     5) ««Если летом я поеду в деревню или в санаторий, то я не поеду в  туристическую поездку».

• Решить задачи средствами алгебры логики. 

1.В процессе составления расписания уроков учителя высказали свои пожелания. Учитель русского языка хочет проводить первый или второй урок, учитель математики – первый или третий, а учитель физкультуры – второй или третий урок. Сколько существует возможных вариантов расписания и каковы они?

Решение. Введем обозначения: А – 1-й урок русского языка, В – 2-й урок русского языка,  - 1-й урок математики, С – 3-й урок математики,  - 2-й урок физкультуры,  - 3-й урок физкультуры. Составим логическую формулу, опираясь на условие задачи: (АvВ) & (v C) & (v). Таблица истинности для нее будет иметь вид:

Ответ. Анализируя таблицу, приходим к выводу, что расписание может быть представлено в двух вариантах:

1 урок математика                1 урок русский язык

2 урок русский язык   или     2 урок физкультура

3 урок физкультура               3 урок математика.

2. Только один из подозреваемых участвовал в преступлении.  Известно, что если Иванов не участвовал или Петров участвовал, то Сидоров участвовал; если Иванов не участвовал, то Сидоров не участвовал. Кто участвовал в преступлении?

3. Аня, Вика и Сергей решили пойти в кино. Учитель, хорошо знавший ребят, высказал предложения: Аня пойдет в кино только тогда, когда пойдут Вика и Сергей; Аня и Сергей пойдут в кино вместе или же оба останутся дома; чтобы Сергей пошел в кино, необходимо, чтобы пошла Вика. Когда ребята пошли в кино, оказалось, что учитель немного ошибся: из трех его утверждений истинными оказались только два. Кто из ребят пошел в кино?

4. Намечаются экскурсии в три города А, В и С. Руководитель фирмы сказал: «Неверно, что если будет экскурсия в город В, то не будет экскурсии в город С. Если будет экскурсия в город С, то не будет экскурсии в город А.» В какие города будет проводиться экскурсия?

Практическая  работа 4

по предмету по предмету «Элементы математической логики»

Преподаватель Сипачева О.И.

Тема: Действия над множествами.

Цель работы: знать, что понимают под множеством, уметь выполнять действия над множествами и знать законы действий над множествами.

Ход работы.

Повторить   краткие теоретические сведения и разобрать задачи с решениями. 

                                                               «Ты когда-нибудь видела, как   рисуют множество?

                         - Множество чего? - спросила Алиса.

                                         - Ничего... Просто множество!»

                                                        Льюис Кэрролл “Алиса в стране чудес”

1.1  Множество.  Способы задания множеств.

         Одним из основных исходных понятий математики является понятие множества и его элементов. Множество состоит из элементов. Множества обозначаются большими латинскими буквами: A; B; C..., а их элементы - малыми буквами: a,b,c,…

        Если a является элементом множества A или, что то же самое, a принадлежит множеству A,  то применяют запись aA; в противном случае пишут aA.

        Два множества A и B равны  (A=B), если они состоят из одних и тех же элементов. Если множества A и B не равны, то применяется запись A  B.

        Множество, содержащее конечное число элементов, называется конечным, в противном случае множество называется бесконечным. Конечное множество, содержащее n элементов, называется n-множеством.

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

а                                                        б

Рис. 1.1.

        Если каждый элемент а множества В, аВ, является элементом множества А, аА, то В называется подмножеством множества А (рис. 1.1, а). Этот факт записывается с помощью знака включения    следующим образом:  ВА.  

Свойства включения

        1. А А;  

        2. если  А В  и  ВС,  то АС  (рис. 1.1, б);

        3. из двух включений ВА и А В следует, что А=В.

        Принято считать, что пустое множество является подмножеством любого множества.

        Если  В А  и при этом ВА, то этому соответствует запись В А и В называется собственным подмножеством А. В решении примера 1.1 все множества, кроме последнего, являются собственными подмножествами множества А.

        Для описания множества A, состоящего из элементов a1,a2,...,an,... обычно применяется запись A={a1,a2,...,an,...}, причём порядок элементов в фигурных скобках не имеет значения; обычно он определяется соображениями наглядности.

        Пример. В записи множества первых n натуральных чисел Nn={1,2,...,n} удобно располагать числа в возрастающем порядке, хотя при этом надо иметь в виду, что

N3 ={1,2,3}={2,1,3}={3,2,1}.

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

     A ={a/a обладает свойством  P(a)}.

        Пример.  Множество чётных чисел M может быть задано так:

 M={i / i - целое число, которое делится на 2 без остатка}.

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

        Возможно также рекурсивное задание множества, при котором осуществляется последовательное описание элементов через предыдущие. Например, множество натуральных чисел  рекурсивно можно задать так:   N={i / если целое  iN,  то i+1N,  i  1}.

1.2. Операции  над множествами. Законы действий над множествами.

        Объединением двух множеств А и В называется множество вида:

AB ={a / a A  или  a B}(рис. 1.2, а).

        Пересечением двух множеств А и В называется множество вида:

AB={a / a A  и   a B} (рис. 1.2, б).

Если множества А и В  не имеют общих элементов, то AB=.

а                                                        б

Рис. 1.2.

Свойства операций объединения и пересечения

        1. AB = ВА,   AB = ВА  (коммутативность);

        2. (AB)С = A(BС),  (AB)С = A(BС) (ассоциативность).  

        Объединение  и  пересечение  связаны законами дистрибутивности:

A(BC)= (AB)  (AС);      A(BC)= (AB)  (AС).

        По свойству 3 операции включения следует равенство правой и левой частей доказываемого равенства.                                                        

        Для операции объединения множеств нейтральным является пустое множество , а для операции пересечения множеств - универсальное множество U.

        Разность  множеств А и В определяется следующим образом:

 A\B ={a / aA и aB} (рис. 1.3, а).

        Разность не обладает свойством коммутативности; эта операция также не является и ассоциативной.

        Пользуясь понятием универсального множества, можно определить дополнение  к множеству А,  как разность вида:  = U \ A (рис. 1.3, б).

         Пример. Пусть в качестве универсального множества выступает множество целых чисел Z и пусть А - это множество всех чётных чисел. Тогда - это множество всех нечётных чисел.

        Операции объединения, пересечения и дополнения множеств связаны между собой  законами де Моргана:

,     .

  Если  a  ,  то  a  AB.  Это значит, что или  a, или  a, т.е.  a.  Следовательно, .

             С другой стороны,  если  a, то или  a, или  a. Это значит, что a A B , т.е.  a  .  Таким образом,   .

             Из этих двух включений следует первый закон де Моргана.                                     

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

а                                                        б

Рис. 1.3.

Образцы решения задач.

1. Найти  

Решение:

2. Доказать равенство и записать двойственное ему:

Решение:

Преобразуем левую часть:

 Таким образом, левая часть равна правой части, т.е. равенство верно.

Для того чтобы составить равенство, двойственное данному, пользуемся принципом двойственности. Заменим в данном равенстве знак   на   и наоборот. Чтобы не поменялся порядок действий, по другому поставим скобки. Получим двойственное равенство:

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

1. Что понимают под множеством?
2. Способы задания множеств.
3. Какое множество называют пустым? Универсальным?
4. Действия над множествами.
5. Законы действий над множествами.

Задание 1.

1 вариант.

1. Найти  

2. Доказать равенство и записать двойственное ему:

3.Даны множества M, P, T. Каким будет множество , если

.

Найдите его. Изобразите его с помощью кругов  Эйлера.

2 вариант.

1. Найти  

2. Доказать равенство и записать двойственное ему:

3.    Даны множества M, P, T. Каким будет множество , если

.

Найдите его. Изобразите его с помощью кругов  Эйлера.

3 вариант.

1. Найти  

2. Доказать равенство и записать двойственное ему:

3.   Даны множества M, P, T. Каким будет множество , если

4 вариант.

1. Найти  

2. Доказать равенство и записать двойственное ему:

3.Даны множества M, P, T. Каким будет множество , если

.

Найдите его. Изобразите его с помощью кругов  Эйлера.

5 вариант. 1. Найти  

2. Доказать равенство и записать двойственное ему:

3.Даны множества M, P, T. Каким будет множество , если

.

Найдите его. Изобразите его с помощью кругов  Эйлера.

6 вариант.

1. Найти  

2. Доказать равенство и записать двойственное ему:

3.Даны множества M, P, T. Каким будет множество , если

.

Найдите его. Изобразите его с помощью кругов  Эйлера.

7 вариант.

1. Найти  

2. Доказать равенство и записать двойственное ему:

3.Даны множества M, P, T. Каким будет множество , если

.

Найдите его. Изобразите его с помощью кругов  Эйлера.

8 вариант.

1. Найти  

2. Доказать равенство и записать двойственное ему:

3.Даны множества M, P, T. Каким будет множество , если

.

Найдите его. Изобразите его с помощью кругов  Эйлера.

9 вариант.

1. Найти  

2. Доказать равенство и записать двойственное ему:

3.Даны множества M, P, T. Каким будет множество , если

.

Найдите его. Изобразите его с помощью кругов  Эйлера.

10 вариант.

1. Найти  

2. Доказать равенство и записать двойственное ему:

3.Даны множества M, P, T. Каким будет множество , если

.

Найдите его. Изобразите его с помощью кругов  Эйлера.

Задание 2. Заданы множества А, В, С. Какие из утверждений будут верными?

a) Множества A и C не содержат одинаковых элементов.

b) Множества A и C равны ( A C ).

c) Множества В и C равны ( B C ).

d) Множество А является подмножеством множества В. ( A B )

e) Множество С является подмножеством множества А. (C A )

f) Множество С является подмножеством множества B. (C B )

g) Пустое множество является подмножеством множества А. 

i) Множество А конечно.

j) Множество В является бесконечным.

k) Множество В является подмножеством пустого множества/

Вариант 0. A = {1,2,a,b} , B = {2,a} , C = {a,1,2,b} .

Вариант 1. A = {2,3,4, f } , B = {3,4} , C = {4,3} .

Вариант 2. A = {7,9,a} , B = {a,9,7} , C = {7,8,9,a,b} .

Вариант 3. A = {5,6,t} , B = {4,5,6,e,t} , C = {6,t,5} .

Вариант 4. A = {3,4,o} , B = {1,3,4,i,o} , C = {o,1,3,i,4} .

Вариант 5. A = {9,10,h,l} , B = {h,l,9,10} , C = {10,h} .

Вариант 6. A = {3,6,9,u} , B = {6,u,9} , C = {6,u,3,9} .

Вариант 7. A = {6,8,10} , B = {4,6,8,10, k} , C = {8,6, k,4,10} .

Вариант 8. A 5,5,t, B 5,5,t, C 5, k,t,5.

Вариант 9. A 1,t, r, B 2,1,0,t, r, C t,1, r.

Вариант 10. A 3,7,11,d, B 7,11,d, C 11,d,7.

Задание 3.Расположите множества: A B , A \ B , AB C , A/(B C) , в таком порядке,

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

Вариант 1. Заданы произвольные множества А, В, С.

Расположите множества: AB C , A \ B , A B , A , в таком порядке, чтобы

каждое из них было подмножеством следующего за ним.

Вариант 2. Заданы произвольные множества А, В, С.

Расположите множества: B C , C \ A ,C \ (A B) , A B C , в таком порядке,

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

Вариант 3. Заданы произвольные множества А, В, С.

Расположите множества: C , B C , A B C , A C в таком порядке, чтобы

каждое из них включало в себя множество, следующее за ним.

Вариант 4. Заданы произвольные множества А, В, С.

Расположите множества: A B , AB C , A B C , A (B C) , в таком

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

множества.

Вариант 5. Заданы произвольные множества А, В, С.

Расположите множества: A B , A B C , A B C , A (B C) , в таком

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

ним.

Вариант 6. Заданы произвольные множества А, В, С.

Расположите множества: AB , AB , A B C , A , в таком порядке, чтобы

каждое из них содержало предыдущее множество.

Вариант 7. Заданы произвольные множества А, В, С.

Расположите множества: B C , B \ (A C) , B , AB C , в таком порядке,

чтобы каждое из них содержало множество, следующее за ним.

Вариант 8. Заданы произвольные множества А, В, С.

Расположите множества: B C , AB C , B C ,C (B \ A) , в таком

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

множества.

Вариант 9. Заданы произвольные множества А, В, С.

Расположите множества: AB , A B C , A B C , A B , в таком порядке,

чтобы каждое из них было подмножеством следующего за ним.

Вариант 10. Заданы произвольные множества А, В, С.

Расположите множества: AB , B , A B C , B (A \ C) , в таком порядке,

чтобы каждое из них включало в себя предыдущее множество._

Задание 4. Заданы множества А, В.

Найдите: AB , A B , A \ B , B \ A, A, B , A \ ,\ B .

Вариант 0. A 1,2,4,5, k,l, B 2,3,4,5,l,m.

Вариант 1. A 3,t,o,4,5, B 2,3,5,o, p.

Вариант 2. A 5,6,8, y,u, r, B 6,7,8, y,m, r.

Вариант 3. A 1,2,3, f ,h, B 0,1,2,3, f ,l.

Вариант 4. A 3,2,0,1, j, k, B 1,0,1,2, k, p.

Вариант 5. A 4,6,8,10,m,n, B 1,4,7,10,m, r.

Вариант 6. A 2,3,6,7,i, y, B 3,4,5,6,i, y, x.

Вариант 7. A a,b,c,3,6,9, B b,c,d,6,7,8.

Вариант 8. A x, y, z,2,3,4, B 3,4,5, s,t, y.

Вариант 9. A a,2,d,3, k,5, B 1,d,2,a,4,m.

Вариант 10. A 5,2,2,w,o, B 8,5,2,0,o, p.

Задание 5. Принято обозначать:

N – множество натуральных чисел; Q – множество рациональных чисел;

Z – множество целых чисел; R – множество действительных чисел.

Тогда верным утверждением будут…

Вариант 0. a) 2.1N , b) 2.7 Q , c) 5Z , d) 7 R .

Вариант 1. a) 6N , b) 2.3Q, c) 3 Z , d) R .

Вариант 2. a) 2N , b) 5 Q, c) 7 Z , d) 8 R .

Вариант 3. a)1.9N , b) 5,6Q, c) 0.7 Z , d) 3 R .

Вариант 4. a) 7 N , b) Q, c) 3 Z , d) 4R .

Вариант 5. a) 3N , b) 11Q , c) 15Z , d) 7 R . 

Вариант 6.а) 4,3N ; b)3.14Q , c) 15Z , d) 9 R .

Вариант 7. a) 7 N , b) 5.17Q, c) 2.5Z , d) 3R .

Вариант 8. a)8N , b) 16 Q, c) 2Z , d) 11R .

Вариант 9. a) 7.2N , b) 13 Q, c) 6,5Z,  d) 25 R .

Вариант 10. a) 9 N , b)12.

Практическая  работа 5

по предмету по предмету «Элементы математической логики»

Преподаватель Сипачева О.И.

Тема: Мощность конечного множества.

Цель работы: уметь решать задачи с помощью кругов Эйлера.

Ход работы.

Повторить   краткие теоретические сведения и разобрать задачи с решениями. 

1. Повторить   краткие теоретические сведения и разобрать задачи с решениями.

Множество А называют подмножеством множества В, если любой элемент множества В является элементом множества В.

 Графически это выглядит так

 Можно дать другое определение равных множеств. Два множества называются равными, если они являются взаимными подмножествами.

  Рассмотрим операции над множествами и их графическую иллюстрацию

1.  Объединение множеств А и В  изображаем:

1.  Пресечение двух множеств А и В изображаем:

В любой имеющей смысл задаче обычно рассматриваются подмножества некоторого "наибольшего" множества U, которое называют универсальным множеством. Универсальное множество - это самое большее множество, содержащее в себе все множества, рассматриваемые в задаче.

 Множество всех элементов универсального множества  U, не принадлежащих множеству А называется дополнением множества А до U и обозначается Ā

Мощностью конечного множества называется количество его элементов.

 Для конечного множества А через m (A) обозначим число элементов в множестве А.

 Из определение следуют свойства:

 m (A) + m (Ā) = m (E)

 А = В => m(A) = m(B)

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

 M()=m (A) + m (В) – m (А∩В)

m = m (A) + m (В) + m (С)– m (А∩В) - m (А∩С) – m (В∩С) – m (А∩В∩С).

Решение задач с помощью кругов Эйлера.

Этот способ решать задачи придумал в XVIII в. великий Леонард Эйлер.

Задача.

 В олимпиаде по математике приняло участие 40 учащихся, им было предложено решить одну задачу по алгебре, одну по геометрии и одну по тригонометрии. По алгебре решили задачу 20 человек, по геометрии – 18 человек, по тригонометрии – 18 человек. По алгебре и геометрии решили 7 человек, по алгебре и тригонометрии – 9 человек. Ни одной задачи не решили 3 человека.  Сколько учащихся решили все задачи?  Сколько учащихся решили только две задачи?  Сколько учащихся решили только одну задачу?

Решение.

Запишем коротко условие и покажем решение:

 m (Е) = 40; m (А) = 20; m (В) = 18; m (С) = 18;  m (А∩В) = 7; m (А∩С) = 8; m (В∩С) = 9;

m (АВС) = 3 => m (АВС) = 40 – 3 = 37

 Изобразим множества А, В, С (рис.5).

 К1 – множество учеников, решивших только одну задачу по алгебре;

 К2 – множество учеников, решивших только две задачи по алгебре и геометрии;

 К3 – множество учеников, решивших только задачу по геометрии;

 К4 – множество учеников, решивших только две задачи по алгебре и тригонометрии;

К5 – множество всех учеников, решивших все три задачи;

 К6 – множество всех учеников, решивших только две задачи, по геометрии и тригонометрии;

 К7 – множество всех учеников, решивших только задачу по тригонометрии;

 К8 – множество всех учеников, не решивших ни одной задачи.

 Используя свойство мощности множеств и рисунок можно выполнить вычисления:

 m (К5) = m (А∩В∩С)= m (АВС) - m (А) - m (В) - m (С) + m (А∩В) + m (А∩С) + m (В∩С);

 m (К5) = 37-20-18-18+7+8+9=5;  m (К2) = m (А∩В) - m (К5) = 7-5=2

 m (К4) = m (А∩С) - m (К5) = 8-5=3;  m (К6) = m (В∩С) - m (К5) = 9-5=4

 m (К1) = m (А) - m (К2) - m (К4) - m (К5) = 20-2-3-5=10;

m (К3) = m (В) - m (К2) - m (К6) - m (К5) = 18-2-4-5=7;

 m (К7) = m (С) - m (К4) - m (К6) - m (К5) = 18-3-4-5 =6

 m (К2) + m (К4) + m (К6) = 2+3+4=9 – число учеников решивших только две задачи;

 m (К1) + m (К3) + m (К7) = 10+7+6=23 – число учеников решивших только одну задачу.

Ответ: 5 учеников решили три задачи;  9 учеников решили только по две задачи;  23 ученика решили только по одной задаче.

1. Решить задачи:

Задача № 1. В классе 35 учеников. Каждый из них пользуется хотя бы одним из видов городского

транспорта: метро, автобусом и троллейбусом. Всеми тремя видами транспорта пользуются 6 учеников, метро и автобусом – 15 учеников, метро и троллейбусом – 13 учеников, троллейбусом и автобусом – 9 учеников.  Сколько учеников пользуются только одним видом транспорта?

Задача № 2.  Каждый из 35 шестиклассников является читателем, по крайней мере, одной из двух библиотек: школьной и районной. Из них 25 человек берут книги в школьной библиотеке, 20 – в районной.

Сколько шестиклассников:1. Являются читателями обеих библиотек;2. Не являются читателями районной библиотеки;3. Не являются читателями школьной библиотеки; 4. Являются читателями только районной библиотеки;5. Являются читателями только школьной библиотеки?

Задача № 1. Из сотрудников фирмы 16 побывали во Франции,10-в Италии,6-в Англии; в Англии и Италии-5; в Англии и Франции -6; во всех трех странах - 5 сотрудников. Сколько человек посетили и Италию, и Францию, если всего в фирме работают 19 человек, и каждый из них побывал хотя бы в одной из названных стран?

Задача №2.В  трёх     группах 70студентов. Из  них  27  занимаются  в  драмкружке,  32  поют  в хоре,  22  увлекаются  спортом.  В  драмкружке  10 студентов из хора, в хоре 6 спортсменов, в драмкружке 8  спортсменов;  3  спортсмена  посещают  и  драмкружок  и  хор. Сколько  студентов  не  поют  в  хоре,  не увлекаются спортом и не занимаются в драмкружке? Сколько студентов заняты только спортом?

Задача №5. Часть жителей нашего дома выписывают только газету «Комсомольская правда», часть – только газету «Известия», а часть – и ту, и другую газету. Сколько процентов жителей дома выписывают обе газеты, если на газету «Комсомольская правда» из них подписаны 85%, а на «Известия» – 75%?

Задача №3. Первую или вторую контрольные работы по математике успешно написали 33 студента, первую или третью – 31 студент, вторую или третью – 32 студента. Не менее двух контрольных работ выполнили 20 студентов. Сколько студентов успешно решили только одну контрольную работу?

Задача №7. В футбольной команде «Спартак» 30 игроков, среди них 18 нападающих. 11 полузащитников, 17 защитников и вратари. Известно, что трое могут быть нападающими и защитниками, 10 защитниками и полузащитниками, 6 нападающими и защитниками, а 1 и нападающим, и защитником, и полузащитником. Вратари не заменимы. Сколько в команде «Спартак» вратарей?

Задача №8. В магазине побывало 65 человек. Известно, что они купили 35 холодильников, 36 микроволновок, 37 телевизоров. 20 из них купили и холодильник и микроволновку, 19 - и микроволновку, и телевизор, 15-холодильник и телевизор, а все три покупки совершили три человека. Был ли среди них посетитель, не купивший ничего?

Практическая  работа 6

по предмету по предмету «Элементы математической логики»

Преподаватель Сипачева О.И.

Тема: Функции алгебры логики.

Цель работы: знать, уметь

Ход работы.

Повторить   краткие теоретические сведения и разобрать задачи с решениями. 

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

Будем рассматривать логические переменные x1, x2, …, xn, принимающие только два значения: «1» или «0».

Булевой функцией  f (x1, x2, …, xn) называется произвольная функция, аргументами которой являются логические переменные и принимающая только одно из двух значений: «1» или «0».

        Количество булевых функций одного аргумента равно 22 = 4, это функции:

f1(x) = 0,  f2(x) =1,  f3 (x) = x  и  f4(x) = .

Булевых функций двух аргументов всего 24 = 16, а количество булевых функций n аргументов равно .

 Всякой формуле алгебры логики, составленной из элементарных высказываний x1, x2, …, xn  соответствует булева функция f (x1, x2, …, xn), аргументы которой принимают значения истинности соответствующих элементарных высказываний: «1» или «0». Две равносильные формулы алгебры логики определяют одну и ту же булеву функцию, т.к. значения истинности этих формул совпадают для одинаковых значений входящих в них переменных. Для булевых функций можно составлять таблицы значений – всякую булеву функцию n аргументов можно задать таблицей из 2n строк.

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

        Значение булевой функции f (x1, x2) при известных значениях аргументов устанавливается по строке таблицы, соответствующей заданным значениям x1 и x2. Например, для функции f (x1, x2) = x1  x2  значение f (1, 0) = 0, а значение f (1, 1) = 1.

Каждой релейно-контактной схеме (РКС), составленной из переключателей x1, x2, …, xn, можно поставить в соответствие булеву функцию, называемую ее функцией проводимости: 

Функция проводимости РКС задается при помощи формулы логики, соответствующей этой РКС. Например, РКС, изображенная на рис. 2,

имеет функцию проводимости , таблица значений которой имеет вид:

Любая функция п переменных может быть представлена многочленом (полиномом) Жегалкина и это представление единственно.

Образцы  решения:

Записать булеву функцию в виде многочлена Жегалкина. Определить является ли функция линейной. 

Решение:

Преобразуем равенство, используя формулы алгебры логики.

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

Ответ: функция не является линейной; многочлен Жегалкина, соответствующий данной функции:

.

.

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

1. Для закрепления теоретического материала и получения прочных  знаний решить примеры.

18. Построить функцию, двойственную данной:  

Ответ:

19. К какому из классов Поста принадлежит функция

Ответы: а) Р0      б) Р1      в) S     г) ни к какому

18. Построить функцию, двойственную данной:

Ответ:

19. К какому из классов Поста принадлежит функция

Ответы: а) Р0      б) Р1      в) S     г) ни к какому

18. Построить функцию, двойственную данной:

Ответ:

19. К какому из классов Поста принадлежит функция

Ответы: а) Р0      б) Р1      в) S     г) ни к какому

18. Построить функцию, двойственную данной:

Ответ:

19. К какому из классов Поста принадлежит функция

Ответы: а) Р0      б) Р1      в) S     г) ни к какому

Практическая  работа 7

по предмету по предмету «Элементы математической логики»

Преподаватель Сипачева О.И.

Тема: Представление Булевых функций в виде многочлена Жегалкина.

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

Ход работы.

Повторить   краткие теоретические сведения и разобрать задачи с решениями. 

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

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

Образцы  решения: Записать булеву функцию  в виде многочлена Жегалкина. Определить является ли функция линейной.

Решение:

Преобразуем равенство, используя формулы алгебры логики.

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

Ответ: функция не является линейной; многочлен Жегалкина, соответствующий данной функции:

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

1. Определение многочлена Жегалкина.
2. Какой многочлен Жегалкина называется линейным?

Для закрепления теоретического материала и получения прочных  знаний решить примеры.

1.Проверить правильность формул, используя таблицы истинности:

 =;  ; ;

; .

2. Выбрать правило исключения альтернативной дизъюнкции :

Ответы:

3. Найти среди многочленов Жегалкина линейный:

 Ответы:

4. 1в.  1. Представить функцию   в виде многочлена Жегалкина, используя формулы алгебры логики.  Определить, является ли функция линейной.  

2. Построить таблицу истинности для функции , найти СДНФ, упростить ее. Построить контактную схему, реализующую эту функцию. Представить функцию в виде многочлена Жегалкина.

     2в   1. Представить функцию   в виде многочлена Жегалкина, используя формулы алгебры логики.  Определить, является ли функция линейной.  

2. Построить таблицу истинности для функции, найти СДНФ,  упростить ее. Построить контактную схему, реализующую эту функцию. Представить функцию в виде многочлена Жегалкина.

Представить в виде многочлена Жегалкина , построить контактную схему, реализующую эту функцию.

    3в.     1. Представить функцию   в виде многочлена Жегалкина, используя формулы алгебры логики.  Определить, является ли функция линейной.  

2. Построить таблицу истинности для функции, найти СДНФ, упростить ее. Построить контактную схему, реализующую эту функцию. Представить функцию в виде многочлена Жегалкина.

 4в.     1. Представить функцию   в виде многочлена Жегалкина, используя формулы алгебры логики.  Определить, является ли функция линейной.  

2. Построить таблицу истинности для функции, найти СДНФ. Построить контактную схему, реализующую эту функцию. Представить функцию в виде многочлена Жегалкина.

  5в.    1. Представить функцию   в виде многочлена Жегалкина, используя формулы алгебры логики.  Определить, является ли функция линейной.  

2. Построить таблицу истинности для функции, найти СДНФ, упростить ее. Построить контактную схему, реализующую эту функцию. Представить функцию в виде многочлена Жегалкина.

Практическая  работа 8

по предмету по предмету «Элементы математической логики»

Преподаватель Сипачева О.И.

Тема: Классы Поста.

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

Ход работы.

Повторить   краткие теоретические сведения и разобрать задачи с решениями. 

.

Американский математик Эмиль Пост ввёл в рассмотрение следующие замкнутые классы булевых функций:

Функции, сохраняющие константу 0 или 1;

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

Монотонные функции;

Линейные функция.

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

Заметим, что существуют функции, не входящие ни в один из классов Поста. Любая такая функция сама по себе образует полную систему. В качестве примеров можно назвать штрих Шеффера или стрелку Пирса.

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

-Хотя бы одна функция, не сохраняющая 0.

-Хотя бы одна функция, не сохраняющая 1.

-Хотя бы одна нелинейная функция.

-Хотя бы одна немонотонная функция.

-Хотя бы одна несамодвойственная функция.

 Важнейшие замкнутые классы

        Класс функций, сохраняющих константу 0

        Обозначим через T0 класс всех булевых функций f(x1,x2,...,xn), сохраняющих константу 0, то есть функций, для которых выполнено равенство f(0,0,...,0)=0. Очевидно, что функции 0, x, x1 x2, x1 x2, x1 x2 принадлежат классу T0, а функции 1, , x1 x2 в него не входят.

        Поскольку таблица для функций f(x1,x2,...,xn) из класса T0 в первой строке содержит фиксированное значение 0, то в T0 попадает  функций, т.е. ровно половина всех булевых функций.

        Покажем, что T0 - замкнутый класс. Так как он содержит тождественную функцию, то для обоснования его замкнутости достаточно показать, что функция Ф=f(f1,...,fm) принадлежит классу T0, если только f, f1,..., fm  принадлежат этому классу.

        Ф(0,0,...,0)= f(f1(0,0,...,0),...,fm(0,0,...,0))= f(0,0,...,0)=0.



        Класс функций, сохраняющих константу 1

        Обозначим через T1 класс всех булевых функций f(x1,x2,...,xn), сохраняющих константу 1, то есть функций, для которых выполнено равенство f(1,1,...,1)=1. Этому классу принадлежат функции 1, x, x1 x2, x1 x2, x1 x2 и не принадлежат функции 1, , x1x2.

        Покажем, что класс T1 состоит из функций, двойственных функциям из класса T0 (говорят, что класс T1 двойственен классу T0).

        Пусть f(x1,x2,...,xn) принадлежит T1, т.е. выполняется равенство f(1,1,...,1)=1. Тогда, воспользовавшись определением двойственной функции, получим:  f*(0,0,...,0)= (,,...,)= (1,1,...,1)=0. Это значит, что f*(x1,x2,...,xn) принадлежит классу T0.

                                                        

        Из взаимной двойственности классов T0 и T1 следует, что T1 также является замкнутым классом и что он содержит столько же булевых функций, что и класс T0.

        Класс самодвойственных функций

        Класс S включает в себя  все самодвойственные функции, то есть такие функции, для которых выполняется равенство: f(x1,x2,...,xn)=f*(x1,x2,...,xn). Очевидно, что функции x и  самодвойственные (см. табл. 1.7). Менее тривиальным примером самодвойственной функции является функция h(x1,x2,x3)=x1x2  x1x3  x2x3. Покажем, что это действительно так.

        Составим двойственную к  функцию * и преобразуем ее:

h*(x1,x2,x3) = (x1x2) & (x1x3) & (x2x3) = (x1x2x3) & (x2x3) = x1x2  x1x3  x2x3 = h(x1,x2,x3).

         

        Для самодвойственной функции имеет место тождество: f(x1,...,xn); иначе говоря, на наборах (1,...,n) и , которые называются противоположными, самодвойственная функция принимает противоположные значения.

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

        Докажем, что класс S замкнут. Поскольку он содержит тождественную функцию, достаточно показать, что функция Ф=f(f1,...,fm) является самодвойственной, если функции f, f1,..., fm самодвойственны. Последнее устанавливается непосредственно:

        Ф*= f*(f1*,...,fm*)= f*(f1,...,fm)= f(f1,...,fm)= Ф.

Класс монотонных функций

        Для двух наборов =(1,...,n)  и =(1,..., n),  выполнено отношение предшествования , если 11, ..., nn и хотя бы в  одной координате  i  выполнено условие i < i.

        Пример. (0, 1, 0, 1)  (1, 1, 0, 1), а наборы  (0, 1) и (1, 0) не сравнимы.

        Очевидно, что отношение предшествования рефлексивно, антисимметрично, транзитивно и представляет собой, таким образом, отношение частичного порядка на множестве Bn=BB...B.

        Функция f(x1,...,xn) называется монотонной, если для любых двух наборов  и  таких, что , имеет место неравенство: f()f().

Например, функции 0, 1, x, x1x2, x1 x2 монотонные, а функции , x1 x2, x1x2 монотонными не являются.

        Обозначим через M множество всех монотонных функций. Покажем, что класс монотонных функций замкнут. Поскольку тождественная функция принадлежит множеству M, то достаточно показать, что функция Ф=f(f1,...,fm)  является монотонной, если функции f, f1,..., fm монотонны.

        Пусть  и  - два набора длины n значений переменных x1,...,xn, причем . Так как  функции f1,..., fm монотонны, то выполняются соотношения fi()fi() при 1  i  m, , поэтому набор (f1(),..., fm()) предшествует набору (f1(),..., fm()) или эти наборы равны.

        В обоих случаях в силу монотонности функции f справедливо неравенство:

f (f1(),..., fm())   f (f1(),..., fm()),

откуда следует, что Ф ()   Ф (), т.е. Ф - функция монотонная.

                

        Наборы  и  называются соседними по i-й координате, если

=(1,..., i-1, i, i+1,... n),        = (1,..., i-1, , i+1,... n).

Класс L линейных функций

        Он содержит функции 0, 1, x, , x1x2 и не содержит функций x1x2 и x1 x2. Выше было показано, что этот класс также замкнут.

        Таблица 1 не содержит двух одинаковых столбцов. Это  хорошо иллюстрирует тот факт, что замкнутые классы T0, T1, S, M и L попарно различны (знак “+” здесь показывает, что функция содержится в классе, а “-” обозначает обратную ситуацию).

Таблица 1

Система функций {f1, f2,..., fk} называется функционально полной, если любая булева функция может быть записана в виде формулы через функции этой системы.

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

Теорема о функциональной полноте. Для того, чтобы система функций  была полной, необходимо и достаточно, чтобы она целиком не содержалась ни в одном из пяти замкнутых классов T0, T1, S, M и L.

Каждая функция из P2 может быть выражена при помощи полинома по модулю 2.

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

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

        Пример.                x | y =  =  = (xy) 

Следовательно, множество всех формул можно разбить на классы эквивалентности таким образом, что все формулы, входящие в один класс, соответствуют одной и той же булевой функции; поэтому если функции, соответствующие некоторым формулам, равны, то сами эти формулы называют эквивалентными. Запись = означет, что формулы  и   эквивалентны.

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

1. Какие существуют классы Поста?
2. Определения функций, принадлежащих различным классам Поста.

Задания.

Определить к каким классам Поста относятся булевы функции:

1в.

1.

2.

     2в.

1.  

2.

    3в 

1.

2.  

    4в. 

1.

2.

5в

1 .

2.

6в

1 .

2.  

    7в. 

1.

2.

         8в. 

1.  

2.

     9в 

1.

3.

   10в. 

1.

3.

     11в. 

1.  

2.

12в.

1.

2.

13в.

1.

2.

      14в 

1.

2.

15в 

1.

2.

Практическая  работа 9

по предмету по предмету «Элементы математической логики»

Преподаватель Сипачева О.И.

Тема: Приложение алгебры логики:  релейно-контактные схемы.

Цель работы: знать законы алгебры Буля, уметь составлять РКС для высказываний, записывать высказывания по данным РКС.

Ход работы.

Повторить   краткие теоретические сведения и разобрать задачи с решениями. 

1. Краткие теоретические сведения.

Релейно-контактной схемой (РКС) или переключательной схемой называется схематическое изображение устройства, состоящего из следующих элементов:

1. переключателей (контактов, реле, ламп и др.);
2. соединительных проводников;
3. входов-выходов (полюсов РКС).

Рассмотрим простейшую РКС, содержащую один переключатель Р. Если переключателю Р поставить в соответствие высказывание х: «Переключатель Р замкнут», то истинному значению х (х = 1) будет соответствовать замкнутое состояние переключателя, при котором РКС проводит ток, т.е. импульс, поступающий на вход, может быть снят на выходе. Значению х = 0 будет соответствовать разомкнутое состояние РКС (ток не проводится). Каждой РКС, состоящей из нескольких переключателей, можно поставить в соответствие высказывание, выраженное некоторой формулой А, таким образом, что истинному значению формулы (А = 1) будет соответствовать замкнутое состояние РКС, а значению А = 0 – разомкнутое состояние. Примеры таких соответствий приведены в таблице.

Простейшие РКС и соответствующие им формулы логики.

Из простейших РКС путем их последовательного и параллельного соединения могут быть построены более сложные переключательные схемы.

        Доказано, что любая формула алгебры логики может быть преобразована к виду, содержащему только операции отрицания, конъюнкции и дизъюнкции. Это позволяет изображать логические формулы при помощи РКС, а РКС задавать формулами.

        Например, согласно формулам основных равносильностей

x  y º Ú y    и     x  y º (x  y)  (y  x),

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

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

1. Образец решения.

Пример.

Упростить РКС, изображенную на рис. 2.

Решение. Запишем соответствующую РКС формулу, используя таблицу простейших РКС и соответствующих им формул логики:

.

Упростим формулу, используя основные равносильности:

.

Таким образом, . Построим РКС, соответствующую упрощенной формуле (рис. 3).

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

1. Что называется  релейно-контактной схемой.
2.  Простейшие РКС и соответствующие им формулы логики.

1.  Задания.

1. Задать релейно-контактной схемой формулу, соответствующие таблице истинности:

1. Задать формулу алгебры логики релейно-контактной схемой:
2. Записать формулу алгебры логики, соответствующую данной релейно-контактной схеме, упростить ее, если это возможно и нарисовать новую схему по упрощенной формуле.

а).

б).

в).

1. Придумать задания аналогичные 1,2,3 и выполнить их.