UML_4822 дм практикум

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

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

Считывание минитермов с карты Карно осуществляется по простому правилу. Клетки, образующие S-куб, дают минитерм (n-S)-го ранга, в который входят те (n-S)-переменные, которые сохраняют одинаковые значения на этом S-кубе. Переменные, которые не сохраняют свои значения на S-кубе, в минитерме отсутствуют. Различные способы считывания приводят к различным представлениям функции в ДНФ.

Пример 224. Покажем, как с карты Карно могут быть считаны минитермы различными способами.

Пример 225. Минимизировать при помощи диаграммы Вейча (карты Карно) булеву функцию:

f x1, x2 , x3, x4 x1x2 x3x4 x1x2 x3x4 x1x2 x3x4 x1x2 x3x4 x1x2 x3x4 x1x2 x3x4

x1x2 x3x4 x1x2 x3x4 x1x2 x3x4 x1x2 x3x4 x1x2 x3x4.

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

101

x2 x2

Для покрытия, показанного на рисунке, минимизированная функция запишется как f x1, x2, x3, x4 x3x4 x1x2 x2x3 x3x4 .

Задача 226. Минимизируйте при помощи диаграммы Вейча (карты Карно) булевы функции:

1)f x1, x2, x3 x1x2x3 x1x2x3 x1x2x3 x1x2x3 x1x2x3 ;

2)f x1, x2, x3 x1x2x3 x1x2x3 x1x2x3 x1x2x3 x1x2x3 ;

3)f x1, x2, x3 x1x2x3 x1x2x3 x1x2x3 x1x2x3 x1x2x3 ;

4)f x1, x2, x3 x1x2x3 x1x2x3 x1x2x3 x1x2x3 x1x2x3 .

5)f x1, x2, x3, x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 ;

6)f x1, x2, x3, x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4

x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 ;

7) f x1, x2, x3, x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 ;

8) f x1, x2, x3, x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 ;

9)f x1, x2, x3, x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 ;

10)f x1, x2, x3, x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4

x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 ;

11)f x1, x2, x3, x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4

x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 ;

12)f x1, x2, x3, x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4

x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 x1x2x3x4 ;

102

4.ЛОГИКА ПРЕДИКАТОВ

4.1.Обоснование прикладной значимости формальной логики

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

Изучение основ логики предикатов (ЛП) начнем с обоснования ее прикладной значимости на основе анализа ограничений логики высказы-

ваний (ЛВ) [1-4, 6, 10].

В логике исчислений высказывания рассматриваются как нераздельные целые и с точки зрения их истинности или ложности. Мы не можем отделить логическую структуру этих рассуждений от их конкретного содержания.

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

-сведением сложных высказываний к элементарным;

-последние рассматриваются как целые нерасчлененные объекты, хотя могут и не являться самыми простыми элементарными рассуждениями;

-не отличает высказывания, выражающие свойства предмета, от высказываний, выражающих отношения между предметами;

-не дает средств для выражения свойств и отношений.

Изучение логических операций посредством логики высказываний осуществляется только при одной фиксированной ситуации, после чего все высказывания делятся на истинные и ложные (для этой ситуации) и мы имеем дело с двухэлементной булевой алгеброй. Несмотря на большую важность и значимость логики высказываний, она оказывается слишком ограниченной для описания и изучения даже простейших заключений науки и практики. В рамки ЛВ не укладываются ни аристотелевская теория силлогизмов [20], ни простейшие заключения арифметики и геометрии, не говоря уже о довольно сложных логических выводах, с которыми приходится сталкиваться в процессе проектирования информацион- но-управляющих систем, а также в повседневной жизни. Такие примеры приведены в [4, 6, 10].

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

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

103

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

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

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

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

ЛП, как и традиционная формальная логика, расчленяет элементарное высказывание (если считать его предложением) на субъект (буквально - подлежащее) и предикат (буквально - сказуемое, хотя оно может выступать в роли определения). Субъект - это то, о чем что-то утверждается в высказывании; предикат - это то, что утверждается о субъекте.

Покажем ограниченные возможности средств ЛВ на примерах.

1)Правильность рассуждения «Всякое число - рациональное число; 1 - целое число; 1 - рациональное число» нельзя установить средствами ЛВ, так как в нем посылки и заключение с точки зрения этой логики - элементарные высказывания, рассматриваются как целые, неделимые, без учета их внутренней структуры.

2)Нетрудно заметить, что рассуждение «»Всякий ромб - параллелограмм; ABCD - ромб, следовательно, ABCD - параллелограмм», хотя отличается по содержанию от рассуждения 1), имеет ту же структуру и следование заключения из посылок в этих рассуждениях определяется именно их структурой, а не содержанием.

Выводы:

На языке ЛВ нельзя отделить логическую структуру этих рассуждений от их конкретного содержания, нельзя выразить схему этих рассуждений.

Если бы мы попытались это сделать, заменяя каждое элементарное высказывание переменной, то каждое из рассуждений 1), 2) приняло бы форму «Из p и q следует r».

Очевидно, что такое представление рассуждений не дает нам возможность выяснить, действительно ли заключение r следует из посылок p и q, так как в нем не отражена структура посылок и заключения.

104

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

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

- простые высказывания выражают, что некоторые объекты (или объект) обладают некоторыми свойствами или же они находятся между собой в некоторых отношениях. Понятия «свойство» и «отношение» рассматриваются как частные случаи понятия «предикат».

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

«Три - простое число», «Сократ - грек»,

«Платон - ученик Сократа» и т.д.

С точки зрения грамматики они состоят из подлежащего («три», «Сократ», «Платон») и сказуемого («есть простое число», «есть грек», «есть ученик Сократа»). Подлежащее является наименованием некоторого объекта (конкретного или абстрактного), сказуемое выражает некоторое свойство. Основным для ЛП является второй член предложения - сказуе- мое-свойство.

Как же ЛП трактует это понятие «свойство»? Она рассматривает его как некоторую функцию. Возьмем первое высказывание «3 - простое число» и отметим, что оно истинно, а затем заменим его высказыванием «4 - простое число», которое ложно. А если заменить в этих высказываниях конкретные числа (3,4) переменной х для чисел из множества N, то получим высказывательную форму «х - простое число», обращающуюся в истинное или ложное высказывание при подстановке вместо х какогонибудь ее значения из N.

P

N {И , Л}, или функцию Р: х Р(х), х N, P(x) {И,Л}, определенную на множестве N и принимающую значения из множества {И,Л}. Такая функ-

105

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

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

Определение. Множество М, на котором задан предикат, называется областью определения предиката.

Определение. Множество Ip М, на котором предикат принимает только те истинные значения, называется областью истинности предиката

Р(х): Ip={x: x M, P(x)=1}

Предикат Р(х) называется тождественно истинным (тождественно ложным) на множестве М, если Ip = М (Ip = ).

Определение. Двухместным предикатом Р(х, у) называется логическая функция двух переменных х и у, определенная на множестве М=М1 М2 и принимающая значения из множества {И, Л}.

С помощью двухместного предиката выражаются отношения между двумя предметами х и у.

Например,

Р1(х, у) - «x<y» - предикат «меньше»; Р1(х, у) - «x=y» - предикат равенства.

Эти предикаты определены на множестве R2=R R.

F1(х, у) - «x||y» - предикат параллельности прямых х и у определен на множестве прямых, лежащих на плоскости.

Отношение между субъектами х и у, заданное логической функцией

P

R2 {И , Л}, может быть задано таблицей. Например, для предиката P(x<y) таблица будет иметь вид:

Область истинности этого предиката - подмножество R2: M[P(x,y)]={(1,2), (1,3), (1,4), (2,3), (2,4), (3,5), ...}.

Аналогично определяется n-местный предикат.

106

Определение. n-местным предикатом называется всякая функция n переменных Q(x1, x2, ..., xn), определенная на множестве М=М1 М2 ... Мn

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

Как и для одноместных предикатов, так и для n-местных предикатов можно определить область истинности, понятие тождественно истинного

итождественно ложного предиката.

Итак, n-местный предикат P(x1, x2,..., xn) является неоднородной двузначной логической функцией. Аргументы x1, x2,..., xn представляют собой объекты из множеств их определения Х1, Х2,..., Хn, то есть х1 Х1, х2 Х2,..., хn Хn и называются предметными переменными. Конкретные значения аргументов называются предметными постоянными.

При замещении аргумента xk (предметной переменной) некоторым его значением а (предметной постоянной) n-местный предикат P(x1, x2,...,

xn) превращается в (n-1)-местный предикат P(x1, x2,..., xk-1, a, xk+1,..., xn) и от переменной xk он уже не зависит. А приписав значения всем переменным

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

Например, трехместный предикат P(x1, x2, x3) - «x1 есть сумма x2 и x3». При подстановке х1=5 исходный предикат переходит в двухместный предикат P(5, x2, x3) - «5 есть сумма x2 и x3», при дальнейшей подстановке х2=2 - в одноместный предикат P(5, 2, x3) - «5 есть сумма 2 и x3». Очевидно, при х3=3 он становится истинным высказыванием, а при всех х3 3 - ложным высказыванием.

Рассмотрим примеры.

1)Так, предикат Р(х) - «х - простое число» определен на множестве N, а множество истинности Ip для него есть множество простых чисел.

2)Предикат Q(x) - «sin x=0» определен на множестве R, а его множе-

ство истинности Ip={k , k Z}.

3) Предикат F(x) - «Диагонали параллелограмма х перпендикулярны» определен на множестве всех параллелограммов, а его множеством истинности является множество всех ромбов.

Задача 227. Среди следующих предложений выделите предикаты и для каждого из них укажите область истинности, если М=R для одноместных предикатов и M=R R для двухместных предикатов:

1.х + 5 = 1;

2.при х = 2 выполняется равенство х2 – 1 = 0;

3.х2 – 2х +1 = 0;

4.существует такое число х, что х2 – 2х +1 = 0;

5.(х + 2)<(3х –4);

6.однозначное число х кратно 3;

107

7.(х + 2) – (3х –4);

8.(х2 + y2)>0.

Решение.

1.Предложение является одноместным предикатом Р(х), IP ={–4}.

2.Предложение не является предикатом. Это ложное высказывание.

3.Предложение является одноместным предикатом Р(х), IP ={ 1 }.

4.Предложение – не предикат. Это истинное высказывание.

5.Предложение – одноместный предикат Р(х), IP =( 3; + ).

6.Предложение – одноместный предикат Р(х), IP ={0; 3; 6; 9}.

7.Предложение не является предикатом.

8.Предложение – двухместный предикат Q(х, y), IQ = R R\{(0,0)}. Необходимо представить подробное объяснение сущности ответов. Пример 228. Какие из следующих предикатов являются тожде-

ственно истинными:

1.(х2 + y2) 0;

2.(х2 + y2) >0.

3.sin2x + cos2x = 1;

4.(x + 1)2 > x –1;

5.х2 + 1 (x + 1)2.

Решение. Очевидно, что предикаты 1); 3); 4) являются тождественно истинными.

В предикате 2) при х = 0, y = 0 неравенство нарушается, а в предикате 5) неравенство нарушается при всех положительных значениях х. Следовательно, предикаты 2) и 5) - не тождественно истинные.

Пример 229. Доказать, что на n-элементном множестве можно определить 2n различных одноместных предикатов.

Решение. Областью истинности предиката может быть любая часть области определения. Следовательно, на n-элементном множестве можно

определить столько предикатов, сколько частей имеет это множество, то есть 2n.

Пример 230. На множестве {0,1}3 определен предикат P(x, y, z): xy=z. Составить таблицу значений этого предиката и определить его область истинности.

Решение представлено в таблице 4.3.

108

М[P(x, y, z)]={(0,0,0),(0,1,0),(1,0,0),(1,1,1)}.

x,y,z

Задача 231. Двухместный предикат, выражаемый уравнением х+у=10, определен на множестве R2, где R={1,2,3,4,5,6,7}. Составьте таблицу значений этого предиката и определите его область истинности. Повторите то же для предиката, определяемого неравенством х+у<10.

Задача 232. Двухместный предикат x<y определен на множестве А В, где А={1,2,3,4,5}, В={3,4,5,6}. Составьте таблицу значений этого предиката и определите его область истинности. То же повторите для предиката х у, определенного на А В.

Задача 233. Найдите области истинности предикатов:

Ответ: 1) Ip= ; 2) Ip={-1; 2}; 3) Ip={-2}.

Задача 234. Даны предикаты Р(х): «х2 – 4 = 0» и Q(х): «3х – 2 < 17».

Найдите области истинности этих предикатов, если их область определения есть: 1) R; 2) N.

Задача 235. На множестве М = {3, 4, 5, 6, 7, 8} заданы два предиката Р(х): «х – простое число» и Q(х): «х – нечетное число». Составьте их таблицы истинности. Равносильны ли предикаты Р(х) и Q(х) на множестве L

= {2, 3, 4, 5, 6, 7, 8}, К = {3, 4, 5, 6, 7, 8, 9}?

Ответ. Предикаты Р(х) и Q(x) равносильны на множестве М, а на множествах L, К не равносильны. А почему?

109

4.2. Операции логики высказываний над предикатами

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

Покажем применение операций ЛВ к предикатам на примерах одноместных предикатов (это рассмотрение сохраняется и для многоместных предикатов).

Пусть на некотором множестве А определены два предиката Р(х) и Q(x). Тогда на этом множестве определены предикаты P x , Р(х) Q(x),

Р(х) Q(x), Р(х) Q(x), Р(х) Q(x), смысл которых получается из определений соответствующих операций над высказываниями.

1) P x обращается в истинное высказывание при всех тех и только тех значениях х из А, при которых Р(х) обращается в ложное высказыва-

2) Р(х) Q(x) обращается в истинное высказывание при всех тех и только тех значения х из А, при которых оба предиката Р(х) и Q(x) обращаются в истинные высказывания, то есть область истинности Р(х) Q(x) - пересечение областей истинности составляющих предикатов Р(х) и Q(x):

110