Версия для печати темы

Автор: blackhard 1.11.2007 0:19

задача такаяисходная информация:строка содержащая булевскую функцию от переменных А,В....,приведенную к нормальной совершенной форме.
задание:вывести таблицу истинности этой функции.
указание:количество переменных и их обозначения должны определяться программно.
подскажите кто может 1)как выглядит функция в нормальной совершенной форме?что значит количество переменных и их обозначения должны определяться программно.
и если можите подскажите еще алгоритм решения.спасибо!

Автор: volvo 1.11.2007 0:53

См. здесь: http://ru.wikipedia.org/wiki/%D0%91%D1%83%D0%BB%D0%B5%D0%B2%D0%B0_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D1%8F#.D0.94.D0.B8.D0.B7.D1.8A.D1.8E.D0.BD.D0.BA.D1.82.D0.B8.D0.B2.D0.BD.D0.B0.D1.8F_.D0.BD.D0.BE.D1.80.D0.BC.D0.B0.D0.BB.D1.8C.D0.BD.D0.B0.D1.8F_.D1.84.D0.BE.D1.80.D0.BC.D0.B0_.28.D0.94.D0.9D.D0.A4.29 и ниже...

Это значит, что ты не должен говорить программе, сколько переменных у тебя будет использоваться, а программа должна работать с произвольной строкой, и сама определять, является ли введенная строка СДНФ или СКНФ. Ну, к примеру, при вводе:

'AB\C+A\B\C' программа должна будет определить, что выражение состоит из трех переменных, а в случае:
'A\B+\AB' - из двух, и соответственно этому строить таблицу... Кстати, задачка-то уже решалась на форуме:

http://forum.pascal.net.ru/index.php?s=&showtopic=15866&view=findpost&p=92850
(но сначала все-таки попробуй решить ее сам)

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

Вот одна из них:
http://forum.pascal.net.ru/index.php?s=&showtopic=6976&view=findpost&p=50607

Вторую с ходу найти не могу, как найду - дам ссылку...

Автор: blackhard 1.11.2007 1:12

спасибо

Автор: blackhard 11.11.2007 16:01

function fromdec(n, radix: longint): string;
var
  s: string;
const
  digit: string[16] = '0123456789ABCDEFQ';
begin
  s := '';
  repeat
    s := digit[(n mod radix) + 1] + s;
    n := n div radix;
  until n = 0;

  while length(s) < 2 do s := '0' + s;
  fromdec := s;
end;
  const
  s: string = 'A*/B+/A*/C*/D+B*/C*D';
type
  tmatrix = array[0 .. 3, 0 .. 3] of 0 .. 1;
 var
  mx: tmatrix;
  p, i: integer;
  mask, sub_s: string;

function matches(s, mask: string): boolean;
var i: integer;
begin
  matches := true;
  for i := 1 to length(s) do begin

    if (mask[i] = 'X') or (s[i] = mask[i]) then {}
    else matches := false

  end;
end;

procedure print_mx(const mx: tmatrix);
var i, j: integer;
begin
  for i := 0 to 3 do begin
    for j := 0 to 3 do write(mx[i, j]:3);
    writeln;
  end;
end;

procedure fill_mx(var mx: tmatrix;
          first, second: string);
var i, j: integer;
begin
  for i := 0 to 3 do
    for j := 0 to 3 do

      if matches(fromdec(i, 2), first) and matches(fromdec(j, 2), second)
      then mx[i, j] := 1;

end;


{var
  mx: tmatrix;
  p, i: integer;
  mask, sub_s: string; }

begin
  s := s + '+';
  repeat
    p := pos('+', s);
    if p > 0 then begin

      sub_s := copy(s, 1, p-1);
      mask := '';

      for i := 1 to 4 do mask := mask + 'X';

      for i := 1 to length(sub_s) do begin

        if sub_s[i] in ['A' .. 'D'] then
          if (i > 1) and (sub_s[i - 1] = '/') then
            mask[ord(sub_s[i]) - ord('A') + 1] := '0'
          else
            mask[ord(sub_s[i]) - ord('A') + 1] := '1';

      end;

      fill_mx(mx, copy(mask, 1, 2), copy(mask, 3, 2));
      delete(s, 1, p);

    end;
  until p = 0;
  print_mx(mx);
  readln;
end. 

может кто поможет разобраться с этой прогой!? тут она работает с заданной функцией а мне бы надо чтоб функцию вводить с клавиатуры я чето не могу допиреть как тут че работает сильно жестоко для меня а я в этом деле новичек

Автор: volvo 11.11.2007 16:41

Функция задана в переменной (ну, типизированной константе, неважно, она себя все равно ведет как переменная) s, так что для того чтобы задать свою функцию, надо просто ввести ее первой строкой основной программы:

begin

  write('Функция: '); readln(s); { <--- вот это добавь }
  s := s + '+';
  repeat
    p := pos('+', s);

Задание-то не очень подходящее для новичка, так что придется тебе разобраться

Где именно непонятно, что делается?

Автор: blackhard 12.11.2007 0:46

мнеб вначале понять по какому принципу она вообще составляет таблици истинности
например я ввожу функцию A*B*C+\A*\B*C
и выдается вот эта таблица
0 0 0 0
0 0 0 0
0 0 0 0
0 0 1 1
и мне кажется что это неверно

Автор: volvo 12.11.2007 1:31

Ну, начнем с того, что ты выбрал не совсем подходящую тебе программу. Что делает скопированный тобой код (кстати, надо было сначала разобраться, а потом говорить что-то о правильности!) - описано в посте №1 той же темы: http://forum.pascal.net.ru/index.php?s=&showtopic=15866&view=findpost&p=92850

(см. таблицу №2 там)

Тебе же нужно не табличное представление (которое напрямую может использоваться для минимизации методом Карно), а таблица истинности - это совсем разные вещи. Я привел тебе ссылку для примера, КАК ВООБЩЕ работать с подобными заданиями, ты же почему-то решил, что это - написанная именно по твоему заданию "под ключ" программа, которую достаточно просто взять и сдать... Этого не будет. Я "под ключ" теперь программы не пишу.

Автор: blackhard 12.11.2007 2:27

да теперь всепонятно.
вот это как я понимаю задается сама таблица

 tmatrix = array[0 .. 3, 0 .. 3] of 0 .. 1; 

ну а если у меня будет функция допустим А*/В ли другая то выходит что в таблице должно быть 4 строки можно
както сделать чтобы массив задавался уже исходя из входных данных?