GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
65 views

f (X, Y, Z) = X'YZ + XY' + Y'Z'f (X, Y, Z) = X'YZ + XY' + Y'Z' and g (X, Y, Z) = X'YZ + X'YZ' + XYg (X, Y, Z) = X'YZ + X'YZ' + XY

Which one of the following is correct?

  1. Both {f}{f} and  {g}{g} are functionally complete
  2. Only  {f}{f}  is functionally complete
  3. Only  {g}{g}  is functionally complete 
  4. Neither {f}{f}  nor  {g}{g} is functionally complete

I'm working on function f, here are my findings
1. f is not preserving 0  ;  2. f is not preserving 0
3. Checking Linearity
f=0 for X=1 Y=1 Z=0 (Number of ones is even for f=0)
f=1 for X=1 Y=0 Z=0 (Number of ones is odd for f=1)

Linearity satisfied, so the function is not Functional Complete, but for other values of X,Y,Z we can prove non-Linearity and proceed further.
PS: I already read @Arjun's solution but please go through my solution and let me know where im getting it wrong.

asked in Digital Logic by (159 points) 8 | 65 views
u mean u want to chk linearity only

and based on that u want ans right?
Yes using linearity, if a bool function is not linear, will check for monotonicity to check for functional complete

From Wikipedia:-

A Boolean function is linear if one of the following holds for the function's truth table:

  1. In every row in which the truth value of the function is T, there are an odd number of Ts assigned to the arguments, and in every row in which the function is F there is an even number of Ts assigned to arguments. Specifically, f(F, F, ..., F) = F, and these functions correspond to linear maps over the Boolean vector space.
  2. In every row in which the value of the function is T, there is an even number of Ts assigned to the arguments of the function; and in every row in which the truth value of the function is F, there are an odd number of Ts assigned to arguments. In this case, f(F, F, ..., F) = T.

 Can, we conclude that all the function which have, odd no of argument are always, linear?

 

Please log in or register to answer this question.



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Top Users Oct 2017
  1. Arjun

    23396 Points

  2. Bikram

    17078 Points

  3. Habibkhan

    8158 Points

  4. srestha

    6286 Points

  5. Debashish Deka

    5438 Points

  6. jothee

    4978 Points

  7. Sachin Mittal 1

    4772 Points

  8. joshi_nitish

    4344 Points

  9. sushmita

    3964 Points

  10. Rishi yadav

    3804 Points


Recent Badges

Great Question jothee
Notable Question Priyanka23
Great Question khushtak
Good Question Ishrat Jahan
Good Answer Arjun
Revival Arjun
Nice Question Kathleen
Nice Answer janakyMurthy
Renewal janakyMurthy
Renewal Bikram
27,316 questions
35,169 answers
84,075 comments
33,262 users