All Questions
Tagged with propositional-logic algorithms
12 questions
1
vote
0
answers
51
views
Application of a formal definition of $max, min$ to evaluate an expression
For an Algorithms course we are studying propositional calculus. As an excercise we are given formal statements which we are to explain in natural language first and then evaluate with specific values....
- 195
0
votes
1
answer
135
views
Is Conjunctive Normal Form or not?
I have one formula that I do not understand why it is CNF and one that is not CNF, namely.
p && !q (NOT NCF)
and
!!p(CNF).
According to the exercise where I found these examples, 1 is not ...
3
votes
1
answer
170
views
"State of the art" algorithms deciding entailment of propositional formulas?
I fail to find much about how to efficiently calculate whether a propositional formula entails another.
Considering the following two points...
We can check, for each truth assignment which makes the ...
- 213
2
votes
1
answer
143
views
Non-Boolean SAT
I was wondering about the complexity of SAT tests with variables $x_i = 0 \lor 1 \lor 2 \dots \lor n$, with clauses being of the form $x_i = a \implies x_j \neq b$. When $n=2$, we have 2SAT, which has ...
- 405
4
votes
1
answer
602
views
Knight and knaves
I have these in my lecture notes, its about the rules where knights always tell the truth and knaves always lie:
If A says “The statement ‘there is gold on the island’ and the statement ‘I am a ...
- 41
0
votes
1
answer
282
views
Is this possible to solve satisfiability by using Quine McCluskey algorithm to simplify the whole given boolean formula by simplifying subformulas?
In this question
Farewell Stack Exchange suggested to use karnaugh maps to solve the satisfiability problem by simplifying the entire/whole boolean formula by simplifying subformulas until you have ...
user82913
3
votes
1
answer
580
views
How to estimate how many assignments satisfy a given DNF formula using Monte Carlo?
Admittedly, homework.
For the purpose of this question: $\phi$ is a DNF formula similar to this one: $(x_1 \wedge \neg x_3 \wedge x_4) \vee (\neg x_1 \wedge x_2)$ Also $C_i$ is a clause in this ...
- 179
1
vote
1
answer
263
views
How to adapt DPLL to solve HORNSAT?
This question wask asked in a homework of Computer Theory in Rome, Italy.
How to simplify the DPLL algorithm in order to solve HORNSAT?
My Approach:
I know that an Horn clause is an OR of ...
- 187
1
vote
1
answer
1k
views
Is this possible to solve boolean satisfiablility by using karnaugh maps to simplify the whole given boolean formula by simplifying subformulas?
Building karnaugh map for the whole given boolean formula always costs Θ(2n) both time and space complexities, where $n$ is the number of boolean variables in the given boolean formula.
It is ...
5
votes
1
answer
259
views
How to find a minimum set of axioms within a set of propositions?
I have a set of propositions, for example $\{a_1,a_2,\dots,a_n\}$. Some propositions depend on others (for example, $a_1,a_2\Rightarrow a_3$, means if $a_1,a_2$ are true, then $a_3$ is true). I want ...
- 153
2
votes
1
answer
148
views
Learning a small disjunction
I have a boolean function $f: \{0,1\}^n \to \{0,1\}$ that I know takes the form
$$f(x_1,\dots,x_n) = x_{i_1} \lor x_{i_2} \lor \dots \lor x_{i_k},$$
but I don't know the values of $i_1,\dots,i_k$. ...
D.W.♦
- 166k
2
votes
4
answers
4k
views
Resolution and what it means to derive the empty set
When using resolution, if the empty set {Ø} is derived from a formula like {¬x,¬y} {x,y}, does that mean the formula is unsatisfiable?
If this is the case, why is ...
- 469