Задачка на булеву алгебру, которую решил неправильно C++
Задачка:
Решил сделать перебором:
#include <iostream>
using namespace std;
bool func(bool x, bool y, bool z, bool w)
{
return (!y + z + !x * w) == (w == z);
}
int main()
{
cout << "x" << " " << "y" << " " << "z" << " " << "w" << " " << "F" << endl;
for (size_t x = 0; x < 2; x++)
{
for (size_t y = 0; y < 2; y++)
{
for (size_t z = 0; z < 2; z++)
{
for (size_t w = 0; w < 2; w++)
{
if (func(x, y, z, w) == 1)
{
cout << x << " " << y << " " << z << " " << w << " " << "1" << endl;
}
}
}
}
}
}
Вывод программы:
x y z w F
0 0 0 0 1
1 0 0 0 1
1 1 0 1 1
1 1 1 1 1
Немного изменю код программы, чтобы столбцы вывода стали совпадать со столбцами условия.
#include <iostream>
using namespace std;
bool func(bool x, bool y, bool z, bool w)
{
return (!y + z + !x * w) == (w == z);
}
int main()
{
cout << "w" << " " << "y" << " " << "z" << " " << "x" << " " << "F" << endl; //<=== поменял местами x и w
for (size_t x = 0; x < 2; x++)
{
for (size_t y = 0; y < 2; y++)
{
for (size_t z = 0; z < 2; z++)
{
for (size_t w = 0; w < 2; w++)
{
if (func(x, y, z, w) == 1)
{
cout << w << " " << y << " " << z << " " << x << " " << "1" << endl; //<=== поменял местами x и w
}
}
}
}
}
}
Вывод программы:
w y z x F
0 0 0 0 1
0 0 0 1 1
1 1 0 1 1
1 1 1 1 1
Таблица из условия:
Итого видим, что вторая строчка вывода программы равна второй строчке таблицы условия. Но в таблице условия есть первая и третья строчка, а ей может соответствовать только ОДНА строчка из вывода программы (третья). В чем проблема? Моя программа генерирует не все возможные комбинации?
Ответы (2 шт):
Первая строка глубоко противоречива :) - 1 должна получаться при наборах 0100 и 1100.
Первый набор непосредственной подстановкой одной переменной 1 и остальных 0 дает, что это x обязан быть 1. Итак, вторую букву мы определили.
Теперь, подставляя x==1 получаем условие (!y || z) == (w == z). Опять, выбирая поочередно y, z, w равным 1, а остальные - 0, находим, что такого набора не существует (убедитесь сами).
Так что задача решения не имеет.
Программа, которую я набросал, выглядит так -
#include <algorithm>
#include <iostream>
#include <iomanip>
using namespace std;
bool chk(bool a[4])
{
return bool(((!a[2])||a[3])||((!a[1])&&a[0])) == bool(a[0] == a[3]);
}
void F(int p[4])
{
bool a[][4] =
{
{false,true,false,false},{true,true,false,false}, // line 1
{false,false,false,true}, // line 2
// line 3
{false,true,false,false},{false,true,false,true},{false,true,true,false},{false,true,true,true}
};
bool res = true;
for(int i = 0; i < sizeof(a)/sizeof(a[0]); ++i)
{
bool b[4];
b[0] = a[i][p[0]];
b[1] = a[i][p[1]];
b[2] = a[i][p[2]];
b[3] = a[i][p[3]];
res = res && chk(b);
}
if (res)
{
cout << "wxyz"[p[0]] << "wxyz"[p[1]] << "wxyz"[p[2]] << "wxyz"[p[3]] << endl;
}
}
int main()
{
int p[4] = { 0,1,2,3 };
do
{
F(p);
} while(next_permutation(p,p+4));
}
Она и сообщила, что решений нет, ну, а дальше я просто искал противоречивые условия...
Возможно, я как-то не так трактую задание - тогда поясните мне, в чем я неправ, буду думать дальше...
Update
С поправкой Mikhailo да, задача имеет единственное решение - xzyw, новый код -
bool chk(bool a[4])
{
return bool(((!a[2])||a[3])||((!a[1])&&a[0])) == bool(a[0] == a[3]);
}
bool chk(int p[4], bool a[4])
{
bool b[4];
b[0] = a[p[0]];
b[1] = a[p[1]];
b[2] = a[p[2]];
b[3] = a[p[3]];
return chk(b);
}
void F(int p[4])
{
bool a[][4] =
{
{false,true,false,false},{true,true,false,false}, // line 1
{false,false,false,true}, // line 2
// line 3
{false,true,false,false},{false,true,false,true},{false,true,true,false},{false,true,true,true}
};
bool res = (chk(p,a[0])||chk(p,a[1])) && chk(p,a[2]) &&
(chk(p,a[3])||chk(p,a[4])||chk(p,a[5])||chk(p,a[6]));
if (res)
{
cout << "wxyz"[p[0]] << "wxyz"[p[1]] << "wxyz"[p[2]] << "wxyz"[p[3]] << endl;
}
}
int main()
{
int p[4] = { 0,1,2,3 };
do
{
F(p);
} while(next_permutation(p,p+4));
}
Рабочий код, мб кому поможет
#include<iostream>
using namespace std;
int main() {
int x = 0, y = 0, z = 0, w = 0;
cout << "x y z w\n";
for(x = 0; x < 2; x++)
for(y = 0; y < 2; y++)
for(z = 0; z < 2; z++)
for(w = 0; w < 2; w++)
if((((y<=z) | ((1-x) & w)) == (w == z)) == 1)
cout << x << " " << y << " " << z << " " << w << "\n";
}