All Questions
Tagged with propositional-calculus boolean-algebra
322
questions
0
votes
1
answer
248
views
Assistance in proving a tautology using a series of logical equivalences.
I am trying to prove, using a series of logical equivalence rules, that the following formula is a tautology:
$$[a∧(a→b)∧(b→c)]→c$$
Yet despite numerous successes on other tautologies and logical ...
2
votes
1
answer
170
views
Proving $(p\to q)\lor (r\to s) \vdash (p\to s)\lor(r\to q)$ using Fitch notation
I'm supposed to prove the validity of the following
$(p\to q)\lor (r\to s) \vdash (p\to s)\lor(r\to q)$
I'm very new to natural deduction, so I still haven't got a "feel" about it. I can prove ...
- 21
2
votes
1
answer
841
views
Universal 2-bit gates
I'd like to show that there is no set of 2 bit reversible gates which is universal. I'm not sure as to where & how do I start here? I tried to assume by contradiction that such a set exists, thus ...
- 935
4
votes
2
answers
11k
views
is bitwise xor completely associative?
The bitwise xor (exclusive or) operator has the following truth table:
$$
\begin{array}{c|cc}
\text{^}&0&1\\
\hline
0&0&1\\
1&1&0
\end{array}
$$
It is true that if $a,b,c,d$ ...
- 21.9k
6
votes
1
answer
346
views
Construct an OR gate when missing input information
Is there a way to construct an OR gate when the input for one combination is unknown?
For example, suppose that the gate, $X$, outputs for the following inputs, $x_1$ and $x_2$, $x_1 = T$, $x_2 = T$:...
- 391
8
votes
2
answers
1k
views
How many truth tables if there are only $\land$ or $\lor$ for $n$ variables?
For example, if we have three operators $\land, \lor$ and $\neg$. For $n$ variables, there will be $2^{2^n}$ different truth tables. Because for $2^n$ rows of the truth table, there are $2$ choices - $...
- 139
1
vote
2
answers
192
views
Proving that a set with a quaternary logical connective is functionally incomplete (i.e. inadequate)
I am stucked at trying to prove that the set $\{N\}$ of one logical connective is inadequate where $N$ is a quaternary connective that is defined as follows:
$N(w,x,y,z)=((x\land y)\land(w\lor z))$
...
- 2,517
2
votes
3
answers
1k
views
Solving this logical puzzle by resolution doesn't work for me
In this document there is a logical puzzle:
If the unicorn is mythical, then it is immortal. If the unicorn is not mythical, then it is a mortal mammal. If the unicorn is either immortal or a ...
- 1,495
2
votes
4
answers
188
views
How to prove this tautology using equivalences?
I am trying to prove that the following is a tautology:
$(A \implies (B \implies C)) \implies ((A \implies (C \implies D)) \implies (A \implies (B \implies D)))$
To make progress, I thought I'd ...
- 197
3
votes
1
answer
2k
views
Proving that a set with a ternary logical connective is functionally incomplete (i.e. inadequate)
I am stucked at trying to prove that the set $\{\lnot ,G\}$ of logical connectives is inadequate where $G$ is a ternary connective that gives $T$ (True) if most of its arguments are $T$.
For example: ...
- 2,517
1
vote
1
answer
53
views
Prove that a boolean function using only $\vee$ and $\wedge$ must attain the value $1$ at least once
Please give me feedback on this
Prove that a boolean function constructed only by using $\vee$
and $\wedge$
(without using $\sim$
) must attain the value $1$ at least once.
- 83
-1
votes
1
answer
4k
views
Boolean Expression Simplification XOR
I have been trying to express XOR in terms of just the '&' and '~' operators. I have managed to get the original XOR definition
(~x & y) | (x & ~y)
down to ~(x & y) & ~(~x & ~y)...
11
votes
1
answer
5k
views
What is the difference between Boolean logic and propositional logic?
As far as I can see, they only employ different symbols but they operate in the same way. Am I missing something?
I wanted to write "Boolean logic" in the tag box but a message came up saying that if ...
- 107
1
vote
0
answers
254
views
Monotonic operators in classical logic
Which means monotony for a logical operator, and affinity, in propositional calculus affinity..., here on wiki do not quite understand!!
- 379
1
vote
0
answers
784
views
Dual formula in propositional logic
There's something I don't understand in my course on propositional logic.
In the case of x being a variable, the definition of its dual is x* = x. Right.
However, further in the course, there's a ...
- 11