М. В. Ломоносова Факультет вычислительной математики и кибернетики Е. И. Большакова, Н. В. Груздева Основы программирования на языке Рефал Учебное пособие

• Название: М. В. Ломоносова Факультет вычислительной математики и кибернетики Е. И. Большакова, Н. В. Груздева Основы программирования на языке Рефал Учебное пособие
• Анкор: qewqe
• Дата: 02.01.2022
• Размер: 0.92 Mb.
• Имя файла: RefalP-1.doc
• Тип: Учебное пособие; #323127
• страница: 20 из 22

5.3.Определение равносильности логических формул

Составить программу, проверяющую равносильность (эквивалентность) двух заданных формул алгебры логики. В формулах используются логические константы TRUE и FALSE, логические переменные и логические операции: отрицания (), конъюнкции (), дизъюнкции (), импликации () и эквиваленции (), а также круглые скобки. В качестве имен переменных могут быть взяты произвольные идентификаторы. Например, логической формулой является запись a1   (b1  a2  c)  (c  b2).

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

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

Две логические формулы называются равносильными, если для любого набора значений входящих в них переменных значения этих формул совпадают (т.е. они реализуют одну и ту же логическую функцию). Например, равносильны формулы x y и x  y.

Логические формулы и реализуемые ими функции могут содержать фиктивные (несущественные) переменные. Переменная x_k является фиктивной для функции f(x₁, … , x_n), n≥1, k≤n, если для любого набора логических значений a₁, … , a_k-1, a_k+1, … , a_n
f(a₁,…,a_k-1,0,a_k+1,…,a_n)  f(a₁,…,a_k-1,1,a_k+1,…,a_n)

Например, фиктивной является переменная x для функции, реализуемой формулой ( x  x )  y  z.

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

• 
  ввод исходных логических формул с клавиатуры или из файла (направление ввода определяется командами пользователя или выясняется в диалоге с ним);
  
• 
  проверку синтаксической правильности введённых формул и выдачу диагностических сообщений в случае обнаружения синтаксических ошибок;
  
• 
  проверку равносильности двух синтаксически правильных логических формул;
  
• 
  нахождение для каждой из двух формул всех фиктивных переменных и их вывод.
  

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

Рефал-программа должна выявлять и диагностировать следующие виды синтаксических ошибок:

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

5.4.Распознавание вхождения логической формулы

Рассматриваются формулы алгебры логики, в которых используются логические константы TRUE и FALSE, логические переменные и логические операции: отрицания (), конъюнкции (), дизъюнкции (), импликации (), а также круглые скобки. В качестве имён переменных могут быть взяты латинские буквы. Например, логической формулой является запись a   (b  c  d) .

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

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

Говорят, что имеет место прямое вхождение логической формулы  в логическую формулу  (т.е. она является подформулой ), если она в точности совпадает с ней или же является операндом одной из применённых в ней логических операций. Например, формула p  q – подформула формулы p  q   r, а формула q   r – нет.

Будем говорить, что имеется непрямое вхождение формулы  в логическую формулу , если существует прямое вхождение в формулу  некоторой эквивалентной формулы , получающейся из  несколькими перестановками операндов бинарных операций конъюнкции и дизъюнкции в формуле . Например, формула q p имеет непрямое вхождение в формулу p  q   r.

Необходимо составить рефал-программу, которая проверяет, содержит ли заданная логическая формула  хотя бы одно вхождение (прямое или непрямое) логической формулы . Программа осуществляет:

• 
  ввод исходных логических формул с клавиатуры или из файла;
  
• 
  проверку синтаксической правильности введённых формул и выдачу диагностических сообщений в случае обнаруженных ошибок;
  
• 
  распознавание прямого вхождения формулы  в , при успешном распознавании выводится формула  , в которой помечена (тем или иным способом) подформула ;
  
• 
  проверку на непрямое вхождение формулы  в , в случае успешной проверки выводится эквивалентная  и помечается её местоположение в формуле ;
  
• 
  анализ, можно ли переименовать в формуле  переменные таким образом, чтобы результирующая формула стала подформулой  – если это возможно, то выводится результирующая подформула и список сделанных в формуле  переименований переменных. Например, формула x y входит в формулу p  q   r при следующем переименовании переменных: x ↔ р, y ↔ q.
  

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