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

• Название: Образовательная программа среднего профессионального образования Комплект контрольнооценочных средств по учебным
• Дата: 03.05.2023
• Размер: 0.96 Mb.
• Имя файла: 0000ec2b-08a5ffa8.docx
• Тип: Образовательная программа; #1105706
• страница: 4 из 6

Законы логики (свойства логических операций)

Следующие формулы являются законами логики.

1. 
   - закон двойного отрицания.
   
2. 
   - закон коммутативности конъюнкции.
   
3. 
   - закон коммутативности дизъюнкции.
   
4. 
   - закон ассоциативности конъюнкции.
   
5. 
   - закон ассоциативности дизъюнкции.
   
6. 
   - закон дистрибутивности конъюнкции относительно дизъюнкции.
   
7. 
   - закон дистрибутивности дизъюнкции относительно конъюнкции.
   
8. 
   - закон отрицания дизъюнкции.
   
9. 
   - закон отрицания конъюнкции.
   
10. 
    - закон отрицания импликации.
    
11. 
    - закон выражения эквивалентности через конъюнкцию и импликацию.
    
12. 
    - закон контрапозиции.
    
13. 
    - закон силлогизма.
    

5. 
   Упрощение формул логики с помощью равносильных преобразований.
   

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

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

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

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

A	B	AB		A
И	И	И	Л	Л	Л
И	Л	Л	И	И	Л
Л	И	И	Л	И	И
Л	Л	И	И	И	И

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

Переменная х, принимающая значения 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

7. 
   Совершенная дизъюнктивная и конъюнктивная нормальные формы (СДНФ и
   

СКНФ)

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

Например, конъюнкции , , 1 являются элементарными. Причем первая элементарная конъюнкция имеет ранг (число литералов) 2, вторая  3, а третья  0.

Следующие конъюнкции: , , , , 0 не являются элементарными.

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

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

Например, ДНФ имеет длину, равную 3.

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

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

Например, для функции , заданной булевым вектором w(F)=(00100111), существуют следующие эквивалентные ДНФ:

, (1)

, (2)

, (3)

, (4)

. (5)

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

Например, (1)  СДНФ функции F.

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

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

8. 
   Представление булевой функции в виде совершенной ДНФ и КНФ,
   

минимальной КНФ, полинома Жегалкина

Для булевой функции, заданной в виде ДНФ , составить СДНФ и выполнить проверку по таблице истинности.

Решение: Применяя закон склеивания (в обратном порядке: ), дополняем конъюнкции, до полных элементарных конъюнкций. Конъюнкцию дополняем в два этапа, так как не является элементарной конъюнкцией:



.

Так как , после сокращения одинаковых конъюнкций получаем СДНФ:

.

Таблица истинности СДНФ

						Элементарные конъюнкции СДНФ
0	0	0	1	0	0
0	0	1	0	0	0
0	1	0	1	1	1
0	1	1	0	0	0
1	0	0	1	1	1
1	0	1	0	0	1
1	1	0	1	1	1
1	1	1	0	0	1

Определение.Полином булевой функции F, в слагаемые которого все переменные F входят только без отрица­ния или только с отрицанием, называется монотонно-поляризован­ным. Причем в первом случае полином функции F называется поло­жительно-поляризованный и обозначается через P(F), а во втором случае - отрицательно-поляризованным и обозначается через Q(F). Полином P(F) иначе называется каноническим полиномом Жегалкина (или в зарубежной научно-технической литературе - формой Рида-Мюллера).

Например, для булевой функции, заданной вектором значений таблицы истинности w(F)=(00100111) полиномы P(F) и Q(F) имеют вид:

,

.

Отметим некоторые свойства монотонно-поляризованных поли­номов P(F) и Q(F) булевой функции :

1. Полиномы P(F) и Q(F) являются для булевой функции F единственными.

2. Полиномы P(F) и Q(F) имеют степень n тогда и только тогда, когда

таблица истинности функции F содержит нечетное число единиц.

3. Число слагаемых полинома P(F) (Q(F)) четно тогда и только тогда, когда

(соответственно ).

9. 
   Понятие полноты множества функций. Замкнутые классы
   

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

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

Теорема. Всякая булева формула, не содержащая отрицаний, представляет собой монотонную функцию отличную от константы; наоборот, для любой монотонной функции, отличной от 0 и 1, найдётся представляющая её булева формула без отрицаний.

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

Теорема. Множество всех монотонных функций является замкнутым классом.

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

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

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

полноту.

Теорема. Если все функции функционально полной системы представимы формулами над системой , то система также функционально полна.

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

.

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

б) Системы (штрих Шеффера) и (стрелка Пирса) являются функционально полными.

.

Таким образом, система сводится к системе , а система - к системе .

в) Система ( умножение по модулю 2, сложение по модулю 2 – см. пункт 1 лекции № 8)) является функционально полной. Поскольку , данная система сводится к .

11. 
    Множества и подмножества.
    

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

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

Множества обычно обозначают большими латинскими буквами (например, A, S, D), а их элементы - строчными (например, a, s, d).

Если элемент х принадлежит множеству А, то это обозначается: х А; в противном случае говорят, что элемент не принадлежит множеству, это обозначается: х А.

Примеры множеств.

1. 
   Множество N - множество натуральных чисел. 1 N. -1 N.
   
2. 
   Множество L - множество букв русского алфавита.ф L. v L.
   

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

Множества можно задавать следующими способами.

1. 
   Перечисление элементов: P={точка, прямая, плоскость, тело}, S={0,1,2}.
   
2. 
   Задание характеристического свойства: L={n|n N и n<7}.
   

12. 
    Операции над множествами
    

Объединение двух множеств А и В – это новое множество, элементами которого являются элементы, принадлежащие множеству А или множеству В. Обозначение: А В.

А В={x| х А или х В}.

Пересечение двух множеств А и В – это новое множество, элементами которого являются элементы, принадлежащие множеству А и множеству В. Обозначение: А В.

А В={x| х А и х В}.

Разность двух множеств А и В – это новое множество, элементами которого являются элементы, принадлежащие множеству А и не принадлежащие множеству В. Обозначение: А \ В.

А \ В={x| х А и х В}.

Обычно элементы множеств выбираются из некоторого достаточно широкого множества U, которое называется универсум. В связи с этим понятием можно ввести операцию дополнение.

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

=U \ A или ={x| х А и х U}.

13. 
    Понятие предикат.
    

Под предикатом предметной переменной х А будем понимать функцию Р(х) на {0,1}. Предикат р (х) называется одноместным предикатом

Например:

Предикат х > 5, x R: при х = 4 предикат обращается в ложное высказывание. При х = 7 предикат обращается в истинное высказывание.

Функция Р (х, у), где х, у А, принимающая значения во множестве {0,1} называется двухместным предикатом.

Например: х<у

14. 
    Логические операции над предикатами.
    

1) Отрицание. - предикат, множеством истинности которого является множество, для которого предикат Р – ложный.



Рис. 1. Область истинности отрицания предиката

2) Конъюнкция Р (х) Q(х) – это предикат, область истинности которого равна М ∩ М .



Рис. 2. Область истинности конъюнкция предикатов

3. 
   Дизъюнкция Р (х) Q(х) – предикат, область истинности которого равна М М .
   

Рис. 3. Область истинности дизъюнкции предикатов

3. 
   ИмпликацияР (х) Q(х) – предикат, у которого область истинности совпадает с дополнением разности М и М , т.е. равна ( ).
   

Рис. 3. Область истинности импликаци предикатов

3. 
   Эквиваленция Р (х) Q(х) – предикат, область истинности которого совпадает с объединением пересечения М с М и дополнения к их объединению, т.е. равна - М ∩М .
   

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

Рассмотрим предложения:

В любой треугольник можно вписать окружность.

Всякое число, оканчивающееся на четную цифру, делится на 2.

В этих предложениях встречаются слова «любой», «всякое». Эти слова заменяют специальным символом. Значок называется квантором всеобщности.

- всякий, любой, каждый.

₍ х) Р (х), где х U – запись, говорящая о том, что любой х из предметной области U обладает свойством Р.

Например. Пусть Р (х) предикат, выражающий для х N свойство быть простым числом. Тогда ₍ х) (х N) Р (х) - ложное высказывание «любое натуральное число является простым».

Наряду с квантором всеобщности в логике предикатов рассматривается квантор существования: Его значок <sub>.

(</sub> х) Р (х) – существует такой х, который обладает свойством Р.

Например. Пусть Р (х) предикат, выражающий для х N свойство быть простым числом. Тогда, ₍ х) (х N) Р (х) - истинное высказывание «существует натуральное число, которое является простым».

Операция введения квантора называется операцией навешивания квантора. Навешивание квантора по какой-нибудь переменной понижает местность предиката.

Переменная, по которой навешен квантор, называется связанной.

Например.х<у - двухместный предикат. Навесим квантор:

₍ х) (х N) (х<у) предикат одноместный по переменной у.

Таким образом, понизить местность предиката можно двумя способами.

1. 
   задать предметной переменной конкретное значение.
   
2. 
   навесить кванторы по одной или нескольким переменным.
   

Квантор всеобщности можно рассматривать как обобщение конъюнкции для конечных и бесконечных множеств.

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

16. 
    Построение отрицаний к предикатам.
    

Отрицание. - предикат, множеством истинности которого является множество, для которого предикат Р – ложный.



Область истинности отрицания предиката

17. 
    Понятие бинарного отношения и его свойства.