Có bác nào biết về "Functionally Complete Set" không?

Có bác nào biết về "Functionally Complete Set" không?

Đại khái: FCSet là tập của một nhóm các phép toán có tính chất mọi biểu thức logíc {0,1}n -> {0,1} đều có thể chỉ cần dùng đúng các phép toán này thì đều có thể biểu diễn được.
(Chắc hiểu vậy là không sai nhỉ? )

Vd: {OR, NOT} là một cái FCSet

Mình đang không biết phải làm thế nào để chứng minh chỉ có đúng 2 cái phép toán NOR và NAND là bản thân nó {NOR} và {NAND} là 2 FCSet duy nhất chỉ có 1 phần tử?

Giả dụ như trường hợp định nghĩa phép toán ~ như sau:
1 ~ 1 = 0
1 ~ 0 = 0
0 ~ 1 = 1
0 ~ 0 = 0
Thì có vẻ như nó cũng đúng đúng.. (đang tịt ở đây nên chẳng biết làm sao.. )...

Không biết có bác nào đã từng đọc qua thì có thể bớt chút thời gian vô cùng quý báu để chỉ cho mình biết với....

Rất cảm ơn mọi người đã quan tâm..

Bạn có thể "bổ củi": Có tổng cộng 2^4 = 16 binary operators. Kiểm tra cả 16 cái thì chỉ có 2 chú NOR và NAND là thỏa mãn yêu cầu thôi.

Báo cáo bác là em cũng đang dùng cách bổ củi. Trong 16 chú đó thì mới giết được 12 chú, còn lại 4 chú.
Gồm NOR, NAND (2 cái này thì là cái cần rồi, không xét). Và 2 chú cuối cùng là
x 0 1
0 1 1
1 0 0
x 0 1
0 1 0
1 1 0
2 chú này tương tự nhau, chắc chỉ cần giết 1 chú là được... Vấn đề nằm ở đây: "Làm sao để giết 1 chú trong 2 chú đó..??"

Giá trị của hai chú này phụ thuộc vào mỗi một biến, chú đầu vào biến thứ nhất, chú sau vào biến thứ hai. Dùng qui nạp thấy rằng mọi biểu thức xây dựng bởi một trong hai chú này phụ thuộc vào đúng một biến tự do đầu tiên tính từ bên trái (hoặc phải) trong biểu thức đó. Vậy cả hai chú không chơi được operator x=y chẳng hạn.

Đồng ý với Altus. Ta có thể làm cách khác như sau:
Xuất phát từ f(a_1,...,a_n) = [ f(a_1,...,0) and not(a_n) ] or [ f(a_1,...,1) and a_n ] với mọi f là hàm logic từ {0,1}^n vào {0,1}. Nên ta có { or , not } là một FCSet.
Vì { or , not } là một FCSet nên điều kiện cần và đủ để một nhóm các phép toán logic là một FCSet là phép toán or , not phải biểu diễn được qua những phép toán đó.
Yêu cầu của bạn là tìm FCSet chỉ có 1 phần tử. Gọi phần tử đó là g từ {0,1}^2 vào {0,1}. Ta kiểm tra.
*Trước hết phép toán " not " phải biểu diễn được qua một dãy các phép toán chỉ có g tham gia, ta có not(a_1)= g( ....g (a_i,a_j)....,....g(a_k,a_l)....) với 1=<i,j,k,l=<2.. Ta cho a_1=a_2=a, tức là not(a)=g(...g(a,a),....g(a,a),....) với mọi a thuộc {0,1}. Do đó không xảy ra các trường hợp g(a,a) = 0, g(a,a)=1, hoặc g(a,a)=a với mọi a vì nếu không vế phải luôn đồng nhất 0, 1, hoặc a. Mà chỉ có 2^2 = 4 hàm g(a,a) từ {0,1} vào {0,1}, vậy
g(a,a)=not(a) với mọi a.
* Ta kiểm phép toán " or " phải biểu diễn được qua một dãy các phép toán chỉ có g tham gia, ta có (a_1or a_2) = g( ....g (a_i,a_j)....,....g(a_k,a_l)....) với 1=<i,j,k,l=<2.. Ta cho a_1=a,a_2=not(a), tức là 1=g(...g(a,not(a)),....g(not(a),a),....). Do đó không xảy ra các trường hợp g(a,not(a))=a, g(a,not(a))=not(a) với mọi a vì nếu không vế phải bằng a, bằng not(a) với mọi a nên không thể luôn bằng vế trái bằng 1. Mà chỉ có 2^2=4 hàm g(a,not(a)), vậy
g(a,not(a))=0 hoặc g(a,not(a))=1 với mọi a.
Xảy ra 2 khả năng
Nếu g(a,a)=not(a) và g(a,not(a))=0, hay g(a,b)=[not(a) and not(b)].
Nếu g(a,a)=not(a) và g(a,not(a))=1, hay g(a,b)=[not(a) or not(b)].
Được ht_sp sửa chữa / chuyển vào 22:32 ngày 18/01/2005
Được ht_sp sửa chữa / chuyển vào 22:34 ngày 18/01/2005
Được ht_sp sửa chữa / chuyển vào 00:35 ngày 19/01/2005

Rất cảm ơn Altus và ht_sp.... Mình sẽ tham khảo chỉ dẫn của 2 bạn...