Вычисление логических выраженний.

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

ПЕРВАЯ ГРУППА ЗАДАЧ: Вычисление константных (не содержащих переменных) логических выражений.

Задача1. Описать три реализующие основные булевы операции функции:
Function _or(x,y: Char): Char; //дизъюнкция (например, Writeln( _or(‘0’,’1’) ) выводит 1.
Function _and(x,y: Char): Char; //конъюнкция (например, Writeln( _and(‘0’,’1’) ) выводит 0.
Function _not(x: Char): Char; //отрицание (например, Writeln( _and(’1’) ) выводит 0.

Написать главную программу, которая на основе указанных функций вычисляет значение заданной в виде стринга элементарной константной ФБФ любого из следующих трёх видов: ‘a&b’, ‘a|c’, ‘-a’, где a,b - константы ‘0’ или ‘1’, а знаки &, |, - означают конъюнкцию, дизъюнкцию и отрицание, соответственно (в формуле нет переменных, поэтому она называется константной). Например, если входная строка имеет вид ‘1|0’, то результатом должно быть ‘1’.

При этом, программа должна только вводить исходную строку и выводить результат её вычисления. А для самого вычисления определить функцию:
function LogCalc0(S:String):Char, где S-исходная формула.
Например Writeln( LogCalc0(‘1|0’)) выведет 1.

Задача2. Расширить условие предыдущей задачи, разрешив входные строки в виде константных логических формул произвольной (в пределах стринга) длины. Скобки внутри строки не используются, а порядок операций определяется с учётом их приоритетов (отриц-конъюн-дизъюн).

Эту версию логического калькулятора оформить как функцию: function LogCalc1(S:String):Char.

Например Writeln( LogCalc1( ‘-0|-0&0’ ) ) выведет 1.

Задача3. Расширить условие предыдущей задачи, разрешив использование внутри логических выражений круглых скобок (произвольной «правильной» структуры вложенностей).

Соответствующую версию калькулятора назвать LogCalc2.

Например Writeln( LogCalc2( ‘(-0|-0)&0’ ) ) выведет 0.

ВТОРАЯ ГРУППА ЗАДАЧ: Вычисление логических выражений с переменными.

Будем теперь считать, что заданное логическое выражение (формула булевой функции) содержит в качестве операндов не только константы (0,1), но также, возможно, переменные, обозначенные латинскими малыми буквами. Одна и та же буква может входить в формулу многократно.
Например, логической формулой теперь является стринг: 'a&1&((-b|a)&z)'

Задача4. Описать и протестировать процедуру procedure vars(fbf:String; var vlst: String);, которая по заданной формуле булевской функции fbf формирует упорядоченный список входящих в неё переменных vlst.

Задача5. Описать и протестировать процедуру procedure inargs(vlst: String; var arglst:String);, которая по заданному списку переменных vlst вводит список соответствующих им двоичных значений arglst. При этом, элементы списка arglist должны запрашиваться с клавиатуры, как значения соответствующих переменных из списка vlst.

Например, вызов процедуры inargs('xy',s) должен привести к выводу подсказки:
x=
Затем, после ввода, например 0, должно последовать:
y=
После ввода на этот раз, например, 1, процедура должна завершиться, сформировав результат s='01' .

Задача6. Описать и протестировать процедуру procedure toConst(var fbf: String; vlst: String; arglst:String);, которая по заданной формуле fbf, заданному списку её переменных vlst и списку значений этих переменных arglst заменяет переменные в формуле их значениями, формируя, тем самым, константную логическую формулу.

Например, в результате выполнения:
s:= 'x&(1|-b&x';
toConst( s, 'xb','10') );
получим s= '1&(1|-0&1'

Задача7. Используя выше приведённые подпрограммы, "собрать" из них логический калькулятор - функцию function LogCalc(fbf: String), которая вычисляет значение логического выражения fbf, запрашивая при необходимости значения содержащихся в ней переменных.

ФИНАЛЬНЫЙ ШАГ:

Задача8. Используя необходимые модули из набора задач 1-7 построить процедуру:
procedure TabIst(fbf:String); которая строит таблицу истинности для заданной формулы fbf.

Подсказка. Для генерации в естественном порядке всех двоичных наборов заданной длины (по одному набору на каждую строку), возможно, будет полезно построить 2-3 простенькие подпрограммки. В частности подпрограмму procedure next(var args:String), которая на стринге имитирует прибавление единицы к числу, представленному своим двоичным значением (т.е. переход от одного "двоичного набора" к следующему).
И еще. Здесь наверное удобней воспользоваться top-down подходом к разработки программ - сначала напишите код нужной вам процедуры TabIst, используя как существующие, так и не существующие пока, но желательные для вас подпрограммы, а уж потом, займитесь тем, чего ещё нет.

Никита, разбираю твой код.

Никита, разбираю твой код. Если не трудно, поясни пожалуйста, как будет выполнятся проверка на дублирование?

Вика,

Вот так выполняется проверка на дублирование:

  1. ...
  2. temp:='';  
  3. // например  у нас после сортировки получилась строка vlst = 'aabc'
  4. for i:=1 to length(vlst) do begin // проверка на дублирование элементов
  5.    if pos(vlst[i],temp)=0  then temp:=temp+vlst[i];
  6.  // первый проход по строке vlst: позиция первого элемента 'a' в пустой строке temp  будет 0, добавим этот элемент в строку  temp
  7. // второй проход: позиция второго элемента  'a' в строке temp уже не будет равна 0 , значит мы не добавляем его в строку temp
  8. // третий проход: позиция третьего элемента 'b' в строке temp будет 0, добавляем в строку temp
  9. // и т.д.
  10.   end;                                                                  
  11. ....

Проверку на дублирование можно упростить,

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

  1.  procedure vars(fbf:String; var vlst:String);
  2.   var i,j:byte;
  3.        storage:set of 'a'..'z';
  4.  begin
  5.   storage:=[]; // пустое множество
  6.   for i:=1 to length(fbf) do begin
  7.    if (fbf[i] in ['a'..'z']) and( not(fbf[i] in storage))   then begin
  8.  // если очередной элемент входит во множество ['a'..'z'] и не входит во множество storage, то
  9.     vlst:=vlst+fbf[i]; //добавляем в строку  vlst
  10.     storage:=storage + [fbf[i]];// добавляем во множество  storage
  11.    end;
  12.   end;
  13.   for i := 1 to length(vlst)-1 do  begin  //сортируем строку vlst
  14.    for j:=1 to length(vlst)-i  do begin
  15.     if vlst[j] > vlst[j+1] then begin
  16.      swap(vlst[j],vlst[j+1]);
  17.     end;
  18.    end;
  19.   end;

1-й вариант намного понятнее.

1-й вариант намного понятнее. Спасибо!

Ну, наконец-то, после кошмара

Ну, наконец-то, после кошмара [Втр, 26/02/2013 - 20:56] вспомнили, Никита, о множествах!
Кстати, при желании, можно и без сортировки обойтись:

  1. procedure vars(fbf:String; var vlst:String);
  2.    Var c: Char;
  3. Begin
  4.    vlst:='';
  5.    For c:='a' to 'z' do Begin
  6.      If Pos(c,fbf)>0 Then vlst:=vlst+c
  7.    End;
  8. End;

Вот теперь я за Вику спокоен :-)

Спасибо, Валерий

Спасибо, Валерий Шахамболетович:-)
вот код к задаче 5.
Условие: Описать и протестировать процедуру procedure inargs(vlst: String; var arglst:String);, которая по заданному списку переменных vlst вводит список соответствующих им двоичных значений arglst. При этом, элементы списка arglist должны запрашиваться с клавиатуры, как значения соответствующих переменных из списка vlst.

  1. procedure inargs(vlst: String; var arglst:String);
  2.   var
  3.     i:Byte;
  4.     a,arglst1:string;
  5.   begin
  6.   arglst1:='';
  7.   for i:=1 to length(vlst) do begin
  8.     writeln(vlst[i],'=');
  9.     readln(a);//вводим 1 или 0
  10.     arglst1:=arglst1 +a;
  11.   end;
  12.   arglst:=arglst1;
  13.  end;

Уточняющий вопрос вобщем по

Уточняющий вопрос вобщем по кодам: vlst-это уже упорядоченный список входящих в неё переменных, а temp-это просто список переменных,которые присутствуют в формуле?

Ксения, если ты по поводу 4

Ксения, если ты по поводу 4 задачи, то там список переменных vlst после обмена значений, уже стал упорядоченным, а temp - это новый сформированный список, который требуется получить

Ксения,

temp - это временная переменная, в которой формируется упорядоченный список;
потом vlst:=temp ;
лучше использовать вариант, который привел Валерий Шахамболетович [Ср, 27/02/2013 - 20:10 — VTlyusten]
Данный вариант намного проще тех, которые приводил я.

Всё правильно, Вика. Только

Всё правильно, Вика. Только вот arglst1 лишняя. Можно бы сразу собирать вводимые значения в arglst.

C vlst Вы правы, Ксения. А вот о temp (и о процедурах, его содержащих) забудьте. Рекомендовать к разбору как поучительные могу только две последние версии процедуры args (отправленные в 18:24 и в 19:10 ), в них ни о каком temp не упоминается.

да, вариант Ср, 27/02/2013 -

да, вариант Ср, 27/02/2013 - 18:24 понятен. Т.е. с помощью код к задаче 4 связан с задачами выше, и мы просто можем с помощью него запрашивать значения переменных в алфавитном порядке для введенной формулы? и все?

исправила... procedure

исправила...

  1. procedure inargs(vlst: String; var arglst:String);
  2.   var
  3.     i:Byte;
  4.     a:string;
  5.   begin
  6.   arglst1:='';
  7.   for i:=1 to length(vlst) do begin
  8.     writeln(vlst[i],'=');
  9.     readln(a);
  10.     arglst:=arglst+a;
  11.   end;
  12.  end;

Да Ксения

Именно так

Задача 6:

  1. program Change_of_variables;
  2.  var f,p,z: string;
  3.  
  4. procedure toConst(var fbf: String; vlst: String; arglst:String);
  5.  var i,j:byte;
  6. begin
  7.  for j:=1 to length(vlst) do begin
  8.   for i:=1 to length(fbf) do
  9.    if fbf[i]= vlst[j] then fbf[i]:=arglst[j]
  10.  end
  11. end;
  12. begin
  13.  writeln('Введите формулу:'); // fbfr
  14.  readln(f);
  15.  writeln('Введите список переменных:'); // vlst
  16.  readln(p);
  17.  writeln('Введите список значений:'); // arglst
  18.  readln(z);
  19.  toConst(f,p,z);
  20.  writeln('Данная формула примет вид:' ,f);
  21. end.

вроде это программа наоборот

вроде это программа наоборот все делает...или я не так понимаю?

сначала она запрашивает

сначала она запрашивает список переменных, потом-их значение, а затем выдает в качестве ответа вид формулы

да, Ксюш, так и должно

да, Ксюш, так и должно быть:-)

Ксения

procedure vars - формирует упорядоченный список переменных
procedure inargs - уже по списку переменных запрашивает их значения
procedure toConst заменяет переменные в формуле их значениями, формируя, тем самым, константную логическую формулу.

а разве после ввода формулы

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

Ксюш, здесь условие другое

Ксюш, здесь условие другое

Ксения

Как раз для этих целей мы и описали процедуру inargs

Ксения

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

Валерий Шахамболетович

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

да..условие такое и

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

Ксения

Всегда рады помочь....:)))

спасибо:):)

спасибо:):)

Ну что сказать ? Мы близки к

Ну что сказать ? Мы близки к цели. Удачно включившись, Валентин правильно реализовал ещё один модуль (совсем не беда, что с проверочной программой!). Остался последний, нетрудный штрих - собрать всё это в работающий логический калькулятор! Знаю, Никита уже это сделал, но хотел бы, чтобы кто-то ещё.

Кстати, Ксения. Рекомендовал

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

Валерий Шахамболетович, нужно

Валерий Шахамболетович, нужно только функцию описать? Или полностью программу?

Я примерами и спасаюсь)

Я примерами и спасаюсь) задания понятны, просто я сама у себя грубую ошибку допустила, и подумала что код Валентина работает не верно..извините)

Виктория:

Виктория:
Задача7. Используя выше приведённые подпрограммы, "собрать" из них логический калькулятор - функцию function LogCalc(fbf: String), которая вычисляет значение логического выражения fbf, запрашивая при необходимости значения содержащихся в ней переменных.

Вика,полностью калькулятор из

Вика,полностью калькулятор из этих функций:) как мы делали с задачами 1-3 на лаб.занятии.. Этот "АВС" вечно чем то недоволен, после "Procedure" он ожидает оператор(

Задача 7.

Смею предположить что процедура LogCalc примет такой вид...

  1.  function LogCalc(fbf:string):char;
  2.     var vl,arg:string;
  3.  begin
  4.      vl:='';
  5.      arg:='';
  6.      vars(fbf,vl);  //Создаем список переменных
  7.      inargs(vl,arg); // Создаем список значений
  8.      toconst(fbf,vl,arg); // Заменяем переменные на их значения
  9.      logcalc:=logcalc2(fbf)  //  Отправляем в Logcalc2
  10.  end;

Ксюш, ты где-то точку с

Ксюш, ты где-то точку с запятой не поставила

Уж не знаю, где там Ксения

Уж не знаю, где там Ксения точку с запятой не поставила, а вот совершенно точно, что Валентин поставил финальную точку на этом этапе развития нашей большой комплексной задачи.
Всех участников благодарю и поздравляю! Впереди - адаптация и доработка нашего комплекса для решения задачи создания таблиц истинности для заданных ФБФ (точные спецификации условия предоставлю быть может завтра).

P.s.

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

Валерий Шахамболетович,

Валерий Шахамболетович, насколько я понимаю полностью программа должна выглядеть так:

  1. program Logical;
  2. type Bin=set of 0..1;
  3. ...
  4. begin
  5.   writeln('Введите ФБФ:');
  6.   readln(s);
  7.   writeln('Результат= ', LogCalc(s));
  8. end.

=======================

КОММЕНТАРИЙ ОТ VaSh:
Прошу прощения, но поспешно выложенный здесь неряшливый, содержащий многочисленные неточности и недопустимо обширный для непосредственного включения в форум код был вынужден сократить и заменить своей редакцией ...

Марафон.

Начинаю решать задачи с третей по... по какую смогу :))

  1. function LogCalc2(s: string): char;
  2.   var i,k: integer;
  3. begin
  4.   i:=Pos(')',s); //Находим первую закрытую скобку.
  5.   while i<>0 do begin //Пока в строке имеется закрытая скобка, выполним...
  6.     k:=i; //Переприсвоим.
  7.     while s[k]<>'(' do //Пока k-ый элемент в строке не равен последней открытой скобке, выполним...
  8.       k:=k-1; //Идём влево от первой закрытой скобки. Как только наткнёмся на последнюю открытую, то её индекс будет хранится в переменной k.
  9.       s[k]:=LogCalc1(Copy(s,k+1,i-k-1)); //Вычислим значение внутри скобоки.
  10.       Delete(s,k+1,i-k); //Удалим ненужные остаточные элементы для выполнения дальнейших действий.
  11.       i:=Pos(')',s); //Находим первую закрытую скобку теперь уже для новой строки.
  12.       LogCalc2:=s[1]; //Присвоим функции нужное значение.
  13.   end;
  14. end;

Задача #4.

  1. const letters =['a'..'z']; //Множество букв.
  2. procedure vars(fbf: string; var vlst: string);
  3.   var x: char;
  4. begin
  5.   vlst:=''; //Пустая строка. В последствии в неё будем кидать буквы.
  6.   for x in letters do begin //Пробегаем переменной x по все буквам.
  7.     if Pos(x,fbf) > 0 then vlst:=vlst+x //Если буква находится в исходной строке (если буквы нет в строке, то её pos=0), то кидаем её в строку vlst.
  8.   end; //for
  9. end;

Задача #5.

  1. procedure inargs(vlst: string; var arglst: string);
  2.   var i: integer;
  3.       s: string;
  4. begin
  5.   arglst:=''; //Пустая строка. В последствии в неё будем кидать значения букв.
  6.   for i:=1 to length(vlst) do begin //Пробегаем по всем символам.
  7.     writeln(vlst[i], '='); //Выводим символ на экран со знаком '='.
  8.     readln(s); //Вводим символ с клавиатуры.
  9.     arglst:=arglst+s; //Кидаем вводимые значения с клавиатуры с строку arglst.
  10.   end; //for
  11. end;

Задача #6.

  1. procedure toConst(var fbf: string; vlst: string; arglst:string);
  2.   var i,k,j: integer;
  3. begin
  4.   for i:=1 to length(vlst) do begin //Пробегаем значения по строке vlst.
  5.     for j:=1 to length(fbf) do //Пробегаем значения по строке fbf.
  6.       k:=Pos(vlst[i],fbf); //В переменной k хранится позиция первого вхождения i-ого элемента строки vlst в строку fbf.
  7.       while k <> 0 do begin //Пока элемент строки vlst находится в строке fbf выполнить...
  8.         Delete(fbf,k,1); //Удаляем элементы строки vlst в строке fbf.
  9.         Insert(arglst[i],fbf,k); //Вставляем соотвествующие элементы строки arglst на место удалённых элементов.
  10.         k:=Pos(vlst[i],fbf); //Повторяем поиск снова для повторных элементов.
  11.       end; //while
  12.   end; //for
  13. end;

Вот некоторые из функций из

...

Ксения

  1.  type _set= set of '0'..'9';
  2. ...
  3. function SetToStr(suite:_set):string;
  4.   var c:char;
  5.    temp:string;
  6.    i:byte;
  7.  begin
  8.   SetToStr:='';
  9.   temp:='[';
  10.   for c:='0' to  '9' do begin //  идем по '0'..'9'
  11.    if c in suite then begin // если с входит в suite
  12.     temp:=temp+c; // то добавляем во временную строку
  13.     temp:=temp+','; // добавляем запятую
  14.    end;
  15.   end;
  16.   temp[length(temp)]:=']'; // последнему элементу (он является запятой) присвоиваем скобку ']'
  17.   setToStr:=temp; //settostr присвоили временную переменную temp
  18.  end;

спасибо) тоже пробовала

спасибо) тоже пробовала так..не получалось как раз из-за того,что не просто переменную С взяла..а проверяла [k(i)] (это у меня элемент множества-результата) на присутствие в универс. мн-ве..

моя функция Ехpr : при

моя функция Ехpr : при попытке выполнения выводит "выход за границы диапозона типа byte" (строка 21)

Ксюш, возможно дело в версии

Ксюш, возможно дело в версии паскаля. У меня этой ошибки не выдает

ВНИМАНИЕ!

Код Ксении о множествах и комментарии к нему будут удалены как не соответствующие теме форума. В форуме ДМ открыта специальная новая тема о калькуляторе множеств (если хотите, Ксения, скопируйте свой материал туда).
Там же опубликованы 4 первые задачи.

На некоторые последние...

Вика, код Ваш демонстрирующий всю программу - калькулятор удалил. Моя редакция и объяснения там же.

Асхад,
LogCalc2, 12 строка должна быть вынесена из цикла.
Задачи4,6. - программы содержат ошибки (4-я не будет даже компилироваться).
Вообще, всё это уже сделано до Вас и полезней было бы работать над новыми задачами.

Ответ.

Все задачи, которые Я разместил компилируются. По крайней мере в Borland Developer Studio 2006 уж точно. Ладно. Попробуем порешать задачи с множествами.

обязательно, Валерий

обязательно, Валерий Шахамболетович.Не удаляйте пока,пожалуйста))