Курсовая Елфимов МЛ. Курсовой проект по дисциплине Математическая логика и теория алгоритмов Тема Практические задачи математической логики и теории алгоритмов

• Название: Курсовой проект по дисциплине Математическая логика и теория алгоритмов Тема Практические задачи математической логики и теории алгоритмов
• Дата: 03.06.2021
• Размер: 369.02 Kb.
• Имя файла: Курсовая Елфимов МЛ.docx
• Тип: Курсовой проект; #213505
• страница: 6 из 7

4 Релейно-контактные схемы

Под релейно-контактной схемой (РКС)[4] понимается устройство из проводников и двухпозиционных контактов. Оно может быть предназначено, например, для соединения или разъединения полюсов источника тока с некоторым потребителем. Контакты РКС могут быть двух типов: замыкающие и размыкающие. Каждый контакт подключен к некоторому реле (переключателю). Когда реле срабатывает, все подключенные к нему замыкающие контакты замкнуты, а размыкающие контакты разомкнуты; в противном случае наоборот. Каждому реле ставится в соответствие своя булева переменная , которая принимает значение 1, если реле срабатывает, и 0 в противном случае.

Две релейно-контактной схемы называются равносильными, если одна из них проводит ток тогда и только тогда, когда другая схема проводит ток, то есть если обе эти схемы обладают одинаковыми функциями проводимости. Из двух равносильных схем более простой считается та, которая содержит меньшее число контактов [7].

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

Составить релейно-контактные схемы для следующей формулы:



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




Релейно-контактная схема (рисунок 6):

Рисунок 6 – Релейно-контактная схема

5 Исчисление предикатов

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

Одноместным предикатом P(x) называется произвольная функция переменной x, определённая на множестве M и принимающая значение из множества {0, 1}. Множество, на котором определён предикат P(x), называется областью определения предиката. Множество всех элементов x, принадлежащих M, при которых предикат принимает значение «истина», называется множеством истинности предиката P(x).

Двуместным предикатом P(x, y) называется функция двух переменных x и y, определенная на множестве M = M₁*M₂ (M₁, M₂ – области определения переменных x и y соответственно) и принимающая значения из множества {0, 1}. Например, предикат равенства ”x=y” определен на множестве R=R*R (R – множество действительных чисел).

5.2 Кванторные операции

Определим предикат P (x, y) - “число x делится на число y”.x, y Z. Истинность этого высказывания является частичной, так как можно выбрать числа x и y такие, что x не делится на y. А предикат P(x) - “простое число x делится только на самого себя и единицу” является универсально истинным, так является истинным для любого значения x.

В логике предикатов частичная и всеобщая истинность обозначается отдельными специальными знаками – кванторами.

Знак общности ∀ заменяет в словесных формулировках слова: все, всякий, каждый, любой. Знак существования ∃ употребляется вместо слов: хотя бы один, найдется, существует.

Если задан предикат P(x), то особый интерес представляет рассмотрение следующих двух утверждений:

• 
  неопределенное высказывание истинно для всех ;
  
• 
  неопределенное высказывание истинно хотя бы для одного элемента , или другими словами, существует элемент x множества , для которого - истинно.
  

Эти высказывания в короткой форме будут выглядеть соответственно так:

• 
  
  
• 
  
  

Итак, под выражением понимается высказывание, истинное, когда истинно для каждого элемента из множества и ложное в противном случае. Это высказывание уже не зависит от . Под выражением понимается высказывание, которое является истинным, если существует элемент , для которого истинно, и ложным в противном случае.

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