hi,
need help in my Homework those are the questions:
1. let f:{0,1)^n -> {0,1}
Given that f can be computed by a Boolean circuit of a size s, describe a Boolean circuit of size 2s+n that computes f such that all NOT gates are next to Input Gates
2.
let B be the set of al Boolean function from k bits to one bit.
given that f can be computed by a boolean circuit of size s over B
describe a Boolean circuit of size O(s*2^k) that computes f over demorgan basis

 

hi 296,
Welcome to AAC.
As this is homework, please post your best attempt, and then we can help you.
E

 

hi, of course
for 1 I know that by de morgen I can downgrade every NOT gate down by using demorgan rules.
so for each NOT gate that is not next to the input I can use this method until the NOT gate is down,
every time I do this I will get one more NOT gate, I can't think on how to add gates that do nothing if I am not in right amount of gates
in the most "bad" situtaion I will get n new gate each next to input gate so the maximum I can get Is n+s only in specific situation

for 2 I know that for each language {0,1)^n I can make a Boolean function at size(2^n) that can compute the language straight(if each word is in or not) but the problem for me is that I think I can't switch each gate for the right function because each gate in the first circuit have different size of inputs.