Mixing
Prove that nand is functionally complete
Clash Royale CLAN TAG#URR8PPP
up vote
3
down vote
favorite
Can anyone explain to me how to
Prove that nand is functionally complete.
(To wit: if we let $p ∗ q$ mean $¬(p ∧ q)$, show that the other connectives, $∧$, $∨$, $¬$ and $→$ are expressible in terms of $∗$.)
I understand that logical function on a fixed set of inputs has a finite number of cases, but unsure how to put that into context.
logic propositional-calculus
edited Aug 2 at 5:10
user529760
509216
asked Aug 2 at 4:47
user10168997
434
add a comment |Â
up vote
3
down vote
favorite
Can anyone explain to me how to
Prove that nand is functionally complete.
(To wit: if we let $p ∗ q$ mean $¬(p ∧ q)$, show that the other connectives, $∧$, $∨$, $¬$ and $→$ are expressible in terms of $∗$.)
I understand that logical function on a fixed set of inputs has a finite number of cases, but unsure how to put that into context.
logic propositional-calculus
edited Aug 2 at 5:10
user529760
509216
asked Aug 2 at 4:47
user10168997
434
add a comment |Â
up vote
3
down vote
favorite
up vote
3
down vote
favorite
Can anyone explain to me how to
Prove that nand is functionally complete.
(To wit: if we let $p ∗ q$ mean $¬(p ∧ q)$, show that the other connectives, $∧$, $∨$, $¬$ and $→$ are expressible in terms of $∗$.)
I understand that logical function on a fixed set of inputs has a finite number of cases, but unsure how to put that into context.
logic propositional-calculus
edited Aug 2 at 5:10
user529760
509216
asked Aug 2 at 4:47
user10168997
434
Can anyone explain to me how to
Prove that nand is functionally complete.
(To wit: if we let $p ∗ q$ mean $¬(p ∧ q)$, show that the other connectives, $∧$, $∨$, $¬$ and $→$ are expressible in terms of $∗$.)
I understand that logical function on a fixed set of inputs has a finite number of cases, but unsure how to put that into context.
logic propositional-calculus
edited Aug 2 at 5:10
user529760
509216
asked Aug 2 at 4:47
user10168997
434
edited Aug 2 at 5:10
user529760
509216
edited Aug 2 at 5:10
user529760
509216
edited Aug 2 at 5:10
user529760
509216
509216
asked Aug 2 at 4:47
user10168997
434
asked Aug 2 at 4:47
user10168997
434
asked Aug 2 at 4:47
user10168997
434
434
add a comment |Â
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
5
down vote
accepted
$¬pequiv¬(p ∧ p)$
$p ∧ qequiv¬(¬(p ∧ q))$
$p∨qequiv¬(¬p ∧ ¬q)$
$p→qequiv¬p∨q$
Therefore nand is functionally complete.
answered Aug 2 at 5:12
user529760
509216
Forgive me for being pedantic but shouldn't those equality signs be equivalence signs (ie. $equiv$ ) instead?
– Daniel Mak
Aug 2 at 6:18
1
@DanielMak OK, I edited my post. Thanks!
– user529760
Aug 2 at 6:31
1
@DanielMak: That depends on context. In logic one usually keeps the $=$ sign reserved for equality between terms such that there won't be any confusion when we get to predicate logic -- but if one is doing Boolean algebra (or digital circuits or whatever) there's nothing wrong with using $=$ to assert equality between truth values as well.
– Henning Makholm
Aug 2 at 8:38
4
However, I would point out that this answer tacitly assumes that we already know $neg,land,lor,to$ to be a functionally complete set. Hopefully the OP does already know that in his context.
– Henning Makholm
Aug 2 at 8:41
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
accepted
$¬pequiv¬(p ∧ p)$
$p ∧ qequiv¬(¬(p ∧ q))$
$p∨qequiv¬(¬p ∧ ¬q)$
$p→qequiv¬p∨q$
Therefore nand is functionally complete.
answered Aug 2 at 5:12
user529760
509216
Forgive me for being pedantic but shouldn't those equality signs be equivalence signs (ie. $equiv$ ) instead?
– Daniel Mak
Aug 2 at 6:18
1
@DanielMak OK, I edited my post. Thanks!
– user529760
Aug 2 at 6:31
1
@DanielMak: That depends on context. In logic one usually keeps the $=$ sign reserved for equality between terms such that there won't be any confusion when we get to predicate logic -- but if one is doing Boolean algebra (or digital circuits or whatever) there's nothing wrong with using $=$ to assert equality between truth values as well.
– Henning Makholm
Aug 2 at 8:38
4
However, I would point out that this answer tacitly assumes that we already know $neg,land,lor,to$ to be a functionally complete set. Hopefully the OP does already know that in his context.
– Henning Makholm
Aug 2 at 8:41
add a comment |Â
up vote
5
down vote
accepted
$¬pequiv¬(p ∧ p)$
$p ∧ qequiv¬(¬(p ∧ q))$
$p∨qequiv¬(¬p ∧ ¬q)$
$p→qequiv¬p∨q$
Therefore nand is functionally complete.
answered Aug 2 at 5:12
user529760
509216
Forgive me for being pedantic but shouldn't those equality signs be equivalence signs (ie. $equiv$ ) instead?
– Daniel Mak
Aug 2 at 6:18
1
@DanielMak OK, I edited my post. Thanks!
– user529760
Aug 2 at 6:31
1
@DanielMak: That depends on context. In logic one usually keeps the $=$ sign reserved for equality between terms such that there won't be any confusion when we get to predicate logic -- but if one is doing Boolean algebra (or digital circuits or whatever) there's nothing wrong with using $=$ to assert equality between truth values as well.
– Henning Makholm
Aug 2 at 8:38
4
However, I would point out that this answer tacitly assumes that we already know $neg,land,lor,to$ to be a functionally complete set. Hopefully the OP does already know that in his context.
– Henning Makholm
Aug 2 at 8:41
add a comment |Â
up vote
5
down vote
accepted
up vote
5
down vote
accepted
$¬pequiv¬(p ∧ p)$
$p ∧ qequiv¬(¬(p ∧ q))$
$p∨qequiv¬(¬p ∧ ¬q)$
$p→qequiv¬p∨q$
Therefore nand is functionally complete.
answered Aug 2 at 5:12
user529760
509216
$¬pequiv¬(p ∧ p)$
$p ∧ qequiv¬(¬(p ∧ q))$
$p∨qequiv¬(¬p ∧ ¬q)$
$p→qequiv¬p∨q$
Therefore nand is functionally complete.
answered Aug 2 at 5:12
user529760
509216
edited Aug 2 at 6:23
answered Aug 2 at 5:12
user529760
509216
answered Aug 2 at 5:12
user529760
509216
answered Aug 2 at 5:12
user529760
509216
509216
Forgive me for being pedantic but shouldn't those equality signs be equivalence signs (ie. $equiv$ ) instead?
– Daniel Mak
Aug 2 at 6:18
1
@DanielMak OK, I edited my post. Thanks!
– user529760
Aug 2 at 6:31
1
@DanielMak: That depends on context. In logic one usually keeps the $=$ sign reserved for equality between terms such that there won't be any confusion when we get to predicate logic -- but if one is doing Boolean algebra (or digital circuits or whatever) there's nothing wrong with using $=$ to assert equality between truth values as well.
– Henning Makholm
Aug 2 at 8:38
4
However, I would point out that this answer tacitly assumes that we already know $neg,land,lor,to$ to be a functionally complete set. Hopefully the OP does already know that in his context.
– Henning Makholm
Aug 2 at 8:41
add a comment |Â
Forgive me for being pedantic but shouldn't those equality signs be equivalence signs (ie. $equiv$ ) instead?
– Daniel Mak
Aug 2 at 6:18
1
@DanielMak OK, I edited my post. Thanks!
– user529760
Aug 2 at 6:31
1
@DanielMak: That depends on context. In logic one usually keeps the $=$ sign reserved for equality between terms such that there won't be any confusion when we get to predicate logic -- but if one is doing Boolean algebra (or digital circuits or whatever) there's nothing wrong with using $=$ to assert equality between truth values as well.
– Henning Makholm
Aug 2 at 8:38
4
However, I would point out that this answer tacitly assumes that we already know $neg,land,lor,to$ to be a functionally complete set. Hopefully the OP does already know that in his context.
– Henning Makholm
Aug 2 at 8:41
Forgive me for being pedantic but shouldn't those equality signs be equivalence signs (ie. $equiv$ ) instead?
– Daniel Mak
Aug 2 at 6:18
Forgive me for being pedantic but shouldn't those equality signs be equivalence signs (ie. $equiv$ ) instead?
– Daniel Mak
Aug 2 at 6:18
1
1
@DanielMak OK, I edited my post. Thanks!
– user529760
Aug 2 at 6:31
@DanielMak OK, I edited my post. Thanks!
– user529760
Aug 2 at 6:31
1
1
@DanielMak: That depends on context. In logic one usually keeps the $=$ sign reserved for equality between terms such that there won't be any confusion when we get to predicate logic -- but if one is doing Boolean algebra (or digital circuits or whatever) there's nothing wrong with using $=$ to assert equality between truth values as well.
– Henning Makholm
Aug 2 at 8:38
@DanielMak: That depends on context. In logic one usually keeps the $=$ sign reserved for equality between terms such that there won't be any confusion when we get to predicate logic -- but if one is doing Boolean algebra (or digital circuits or whatever) there's nothing wrong with using $=$ to assert equality between truth values as well.
– Henning Makholm
Aug 2 at 8:38
4
4
However, I would point out that this answer tacitly assumes that we already know $neg,land,lor,to$ to be a functionally complete set. Hopefully the OP does already know that in his context.
– Henning Makholm
Aug 2 at 8:41
However, I would point out that this answer tacitly assumes that we already know $neg,land,lor,to$ to be a functionally complete set. Hopefully the OP does already know that in his context.
– Henning Makholm
Aug 2 at 8:41
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2869724%2fprove-that-nand-is-functionally-complete%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password