All Questions
Tagged with propositional-calculus boolean-algebra
37
questions with no upvoted or accepted answers
3
votes
0
answers
102
views
Do the integers 1 and 0 mean different things in Boole's original logic and modern Boolean algebra?
I understand that the modern notion of Boolean algebra was adapted by Peirce, Schroder and others from Boole's logic of classes. Boole spoke of 1 and 0 as representing the Universe of Discourse and ...
2
votes
0
answers
37
views
When are two propositional formulas dependent?
The following question has arisen when considering dependencies induced by probabilistic logic programs:
Let $A_1, \dots, A_n$ be proposition symbols, and let $\Omega_n$ be the set of all truth value ...
2
votes
0
answers
60
views
Are ultrafilters precisely the designated sets in semantics(es) for classical logic?
I'm messing around with ultrafilters to try to understand them better. It seems as if ultrafilters work well as sets of designated truth values in matrix semanticses for classical logic.
This also ...
2
votes
0
answers
253
views
How can I find the CNF of ($A$ and $B$ or $C$) and ($B$ or not $C$) using a Karnaugh map?
$$(A\land B \lor C) \land (B \lor \lnot C)$$
I know how to create the truth table and Karnaugh map of a logic expression. But I couldn't find exactly how to calculate the simplified CNF of it using ...
2
votes
0
answers
68
views
why does a closed circuit represent a false proposition? (Claude Shannon thesis)
In reading through Claude Shannon's paper: A Symbolic Analysis of Relay and Switching Circuits.
As a software engineer, I got confused by Shannon's choice to have 0 as representing a closed circuit, ...
2
votes
0
answers
149
views
How many distinct subsets of binary boolean operators are closed under composition?
Question:
There are $2^4=16$ distinct binary boolean operators. Two operators are regarded the same if one can be obtained from the other by exchanging the operands (input). It is easy to see only $...
2
votes
0
answers
142
views
Boolean algebras as models of (quantifier-free) monadic predicate logic
Suppose we have a Boolean algebra over $n$ bits, meaning when viewed as a vector space over $F_2$, the dimension is $n$.
Then we can define $n$ unary predicates $P_n$ which return the value of the $n$...
1
vote
0
answers
73
views
How to show $\{0, \vee, \leftrightarrow \}$ is functionally complete/ incomplete?
I'd like to provide an attempt, but all I can think off is trying to construct one of the following complete set of boolean functions and have been unsucessful in that. I can only get an additional ...
1
vote
0
answers
92
views
How do I prove this logical equivalence?
$\phi$ is a well formed formula.
f($\phi$) is given by replacing ∧ with ∨ (and vice versa) and 1 with 0 (and vice versa) in $\phi$.
g(f($\phi$)) is given by replacing all literals in f($\phi$) (...
1
vote
1
answer
257
views
Rewriting a boolean expression using different literals
I'd like to implement an algorithm to rewrite a boolean expression as a sum of products of different boolean expressions (expressed as new literals).
Example
Let's say that I have some literals $A_0,...
1
vote
0
answers
68
views
can you help me find the dnf of this expression ? i got messy
I want to find the DNF of the following expression but it got all messy.
I also tried it in wolfram alpha, and of course it showed i really need the steps you need to make to get there $\dots$
This ...
1
vote
0
answers
1k
views
A reduction of 3-CNF down to 2-CNF for boolean satisfiability
Could you please review the following candidate solution for the boolean satisfiability problem?
It is known that 2-CNF has a polynomial solution.
Now consider we have a 3-CNF (AFAIK, it's proven ...
1
vote
0
answers
284
views
How to prove something is not a logical consequence of 2 propositions.
I have a question where I have to show that the third statement is not a logical consequence of the 1st two using a truth table. I've seen how you'd do if there are only two (How to prove logical ...
1
vote
0
answers
51
views
Is this a Boolean algebra? (proof)
Let $B=\{0,1\}$ and the binary operations $\oplus,\cdot$
We define a bijection $\varphi$ s.t.:
$$
\varphi:B \longrightarrow L=\{\mathbf{False},\mathbf{True}\},
$$
$$
\varphi(x):=
\begin{cases}
\...
1
vote
2
answers
194
views
SOP expression simplify
I wanted to know how to simply this SOP expression using Boolean Algebra :
F= A'BC'+A'BC+ABC
I got this answer using K - Map: (A'B+BC), but I want to know how do get it using Boolean Algebra Rules.
...