Questions tagged [propositional-logic]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
20
votes
4answers
5k views

Can proof by contradiction work without the law of excluded middle?

I was recently thinking about the validity of proof by contradiction. I’ve read for the past few days things on intuitionistic logic and Godel’s theorems to see if they would provide me answers to my ...
12
votes
5answers
3k views

Why does soundness imply consistency?

I was reading the question Consistency and completeness imply soundness? and the first statement in it says: I understand that soundness implies consistency. Which I was quite puzzled about ...
5
votes
1answer
359 views

Implementing mathematical theory of arithmetic in Haskell via Curry-Howard correspondence

I have to ask for forgiveness in advance if the whole question doesn't make a lot of sense, but unfortunately, I have no better intuition as of right now and this seems like the best starting point I ...
1
vote
2answers
1k views

how to solve Hoare logic problems

I'm having trouble proving Hoare logic questions as I'm not sure of the process that is taken to prove them. I understand that they're rules such as assignment axiom, pre-condition strengthening, post-...
0
votes
1answer
86 views

Does exist NP language that is Cook Levin deterministic reducible to xor satisfiability in polynomial time?

We say that the language $L$ is Cook Levin deterministic reducible to xor satisfiability in polynomial time if and only if for each word $w\in\Sigma^*:w\in L\iff f(w)\in XORSAT$ where $\Sigma=\{0,1\}$ ...
0
votes
1answer
163 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 ...
0
votes
2answers
4k views

Which of the following expressions is TRUE if and only if NOT all three variables a, b, and c have the same value?

I am trying to solve this problem and I am stuck. I think it is B, but I think I'm wrong. Thanks. Which of the following expressions is TRUE if and only if NOT all three variables a, b, and c have ...
3
votes
3answers
513 views

Does exist any horn formula that is equisatisfiable to the clause that is disjunction of two literals? Does also exist equivalent?

I just and simply want to know if whether or not exist any horn formula that is equisatisfiable to $(p\lor q)$. I would also be interested to know if there also exists equivalent.
3
votes
1answer
328 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 ...
3
votes
2answers
84 views

Why algorithms calculating non-tirivial zeros can't be used as proofs of Riemann Hypothesis?

Recently I was reading again this propositions as types paper by Philip Wadler: http://homepages.inf.ed.ac.uk/wadler/papers/propositions-as-types/propositions-as-types.pdf It gives an impression, ...
1
vote
1answer
90 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 ...
22
votes
11answers
4k views

Why is $A \lor (A \land \neg B) \equiv A$?

I would like to know if there is a rule to prove this. For example, if I use the distributive law I will get only $(A \lor A) \land (A \lor \neg B)$.
-4
votes
1answer
139 views

Valid, unsatisfied or neither? [closed]

How should I create the truth table to solve each of these questions? Maybe can give me an example? $Smoke \implies Smoke$ $Smoke \implies Fire$ $(Smoke \implies Fire) \implies (\neg Smoke \implies \...
1
vote
3answers
61 views

Expressing statements on elephants in propositional logic

If I wanted to create a sentence like: African elephants can carry coconuts; Asian elephants cannot. How would I do that with propositional logic?
2
votes
4answers
654 views

Is it necessary to learn how to prove Mathematical theorems as a CS Student? [closed]

I've just started my undergraduate course and have tried my hands on MIT's OpenCourseWare on Discrete Math on Logic and Proofs. There was a particular question asking to prove Cantor's Theorem: ...
1
vote
1answer
737 views

Question on Predicates and Quantifiers

I am reading from "Discrete Mathematics and Its applications" by Kenneth H. Rosen, 7th edition. Consider the highlighted part in the following example taken from the same book: Question Use ...
1
vote
1answer
317 views

cancel out parts of a formula in CNF (conjunctive normal form)

In this image there is a given formula in DNF and CNF. When I check it on Wolfram Alpha I see that it cancel out (E or D) because of (not A or A) which is colored in red. My question is if it is ...
0
votes
1answer
67 views

Understanding kQBF: changing order of quantification?

2QBF is a problem of determining whether formula $\exists X~\forall Y:\varphi(X,Y)$ is valid. $X$ and $Y$ here are sets of variables. Next, 3QBF asks if formula $\exists X~\forall Y~\exists Z:\varphi(...
0
votes
1answer
58 views

Does every 3CNF propositional formula has an equisatisfiable 2CNF propositional formula

Does every 3CNF propositional formula has an equisatisfiable 2CNF propositional formula?
2
votes
1answer
157 views

Does every 3CNF propositional formula has an equivalent 2CNF propositional formula?

Does every 3CNF propositional formula has an equivalent 2CNF propositional formula? Definitions: 3CNF propositional formula is conjunctive normal form propositional formula, which is just ...
0
votes
0answers
47 views

Resolution with multiple variables

Resolution allows to generate new clauses for an existing set of clauses. In many cases, the rule is simple: ...
0
votes
0answers
112 views

Convert conjunctive normal form to equivalent boolean formula with only NOR gates

Let $\varphi$ be a boolean formula in 3-CNF form (conjunctive normal form with three literals at most per clause). I want to convert it to an equivalent boolean formula that uses only NOR gates with ...
1
vote
1answer
444 views

Convert conjunctive normal form to equivalent boolean formula with only NAND gates

Let $\varphi$ be a boolean formula in 3-CNF form (conjunctive normal form with three literals at most per clause). I want to convert it to an equivalent boolean formula that uses only NAND gates with ...
1
vote
1answer
540 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 ...
1
vote
1answer
39 views

What is the largest possible minimal 3CNF formula as function of the number of variables?

I have already defined here what is minimal 3CNF formula. In the answer to the question, D.W. answered: What you are thinking is wrong. A minimal, unsatisfiable formula can have more than 8 clauses. ...
2
votes
1answer
99 views

What is the set of all maximal 3CNF formulas?

Definition: A maximal 3CNF formula is satisfiable 3CNF formula, but if you conjuct it with another any new different 3 disjuctive literals clause, then the formula becomes unsatisfiable. Please don't ...
1
vote
1answer
413 views

What is the complexity of determining whether or not conjunction of positive CNF and negative CNF is satisfiable?

Definitions: positive CNF is a conjunctive normal form formula, where all literals are positive, i.e. the unary connective ¬ does not exist in the formula. negative CNF is a conjunctive normal ...
0
votes
1answer
234 views

Proving unsatisfiability of a propositional formula

I have a propositional formula $F$ and an assignment of truth variables $A$. The assignment $A$ assigns a truth value to each variable in $F$ and then it can be evaluated. I have a function which for ...
1
vote
1answer
446 views

Is this possible to solve 4SAT in polynomial time? [closed]

I know and admit that this is long, but please read it slow and understand everything. I think that this is one of the most interesting questions asked in computer science ever. I don't expect for ...
2
votes
1answer
137 views

What is the set of all minimal 3CNF formulas?

Definition: A minimal 3CNF formula is an unsatisfiable 3CNF formula with minimum clauses connected by conjunctions, where each clause is disjunction of 3 literals, that is if any of it's clauses is ...
3
votes
2answers
274 views

Model disjunction in a $\{0,1\}$ integer linear program

How can I model logical OR as an integer linear program? $$(y_3 + y_4 + y_5 + y_6 = 2) \lor (y_2 = 1)$$ where $y_i \in \{0, 1\}$, $1$ = True and $0$ = False.
1
vote
0answers
70 views

Refutation of pigeonhole using resolution

I am trying to find a way to refute the pigeonhole formula using resolution. Lets assume that $x_{ij}$ is true if $i^{th}$ pigeon is in $j^{th}$ hole. Thus, with $n$ holes and $n+1$ pigeons, the ...
3
votes
1answer
261 views

“Implied atomic propositions” in propositional boolean formula

Suppose we have a propositional boolean formula F and let M be the set of all models of that formula. I am wondering if there is an efficient way to find all atomic propositions that are implied by ...
1
vote
1answer
47 views

Logic, “and” operator between a set of formulas and a formula

Consider a set $S$ of formulas $\beta_i$ and a formula $\alpha$, if we have a condition such as $S \land \alpha$ is inconsistent what we have to calculate to check the inconsistency of $S \land \alpha$...
1
vote
1answer
367 views

Why is learning DNF harder than learning CNF?

In the PAC-learning setting, it is easy to learn a CNF formula when we know each clause has at most $c$ variables. We go through each positive sample, and eliminate every clause that contradicts the ...
2
votes
1answer
146 views

First Order Logic : Predicates

I have a small problem with the first order logic, in particular, predicate logic Let us take this sentence as an example: ...
1
vote
0answers
259 views

Propositional logic in an SMA* algorithm

I'm trying to implement an SMA* graph search algorithm that I found in a paper here(Rong Zhou, Eric A. Hansen: Memory-Bounded A* Graph Search. FLAIRS-02 Proceedings 203-209) and I would like to ...
2
votes
2answers
449 views

How is implication same as entailment

In propositional logic (Artificial intelligence to be specific) $\alpha$ entails $\beta$ iff $\alpha\Rightarrow\beta$ is a statement. However if I write the truth table for implies ($\Rightarrow$) if $...
0
votes
1answer
414 views

What is the simplification of AB + BC + (~B)C?

AB + C is not the answer. The correct answer is AB + BC. HOW?
2
votes
1answer
56 views

In the Resolution equivalence ($\neg A \implies B, B \implies C \models \neg A \implies C$) must $A$ be negated?

The sheet of equivalences given to us in class provides the the equivalences \begin{array}{|c|c|c|} \hline \text{Resolution} & A \vee B, \neg B \vee C \models A \vee C & \neg A \implies B, B ...
1
vote
0answers
35 views

What does the structure ($S_t^x P$) in this Existantial Instantiation imply, Skolemization?

The sheet of equivalences given to us in class provides the two equivalences \begin{array}{|c|c|c|} \hline \text{Universal Instantiation} & \forall x ~ P(x) \implies {S_t}^x P & \exists y ~ \...
1
vote
1answer
189 views

Breaking down CNF clauses

I have an assignment where i have to encode certain problem to conjunctive normal form so i can solve it by using SAT solver. I have been able to encode my problem correctly but the solver is quite ...
-2
votes
1answer
189 views

Use of hypothesis to prove a tautology

Given $$ (¬(P ∧¬Q)⇒S)∧¬P ∧(R⇒¬S) ⇒ ¬R $$ prove that this is a tautology. One way is to use a hypothesis taken from the proposition itself. As an example: If we want to prove this rule: $P ⇒ (P ∧ Q ≡...
1
vote
2answers
65 views

What these simple rules of logical implications mean

Their are many rules of logics, predicate calculus, inferences and syllogisms which haunt me always. It feels better when I find some sensible name to particular rule which also gives me intuition ...
1
vote
1answer
99 views

Propositional logic and connectives(translating to english) [closed]

I want to know some stuff about translating compound statements to english: For the propositions below: p: You have the flu. q: You miss the final examination. r: You pass the course. I want to ...
3
votes
2answers
326 views

Does mutual exclusion hold in this case?

I entered into a discussion with a friend on the following question, which asks if mutual exclusion holds: Consider two processes: $s_1$ and $s_2$ are two variables, set equal initially. P1: ...
3
votes
1answer
98 views

Contingent sentences can always be true

I have a question about contingent sentences. To my knowledge, contingent sentences are sentences that are neither tautologies nor contradictions. In a textbook I read that a sentence might always be ...
24
votes
7answers
11k views

Why is A implies B true if A is false and B is false?

It seems to me that the 'implies' in English language does not mean the same thing as the logical operator 'implies', in a similar way how 'OR' word in most cases means 'Exclusive OR' in our everyday ...
1
vote
1answer
86 views

How to reduce C′A′B + CAB′ to C′B + CB′?

I faced this Boolean expression: $C'(A'B+A)+C(A'+AB')$ It was solved as follows: $C'(A'B+A)+C(A'+AB')$ $=C'(A+B)+C(A'+B') $ ...by applying absorption laws $(I)$ $=C'A+C'B+CA'+CB'$ $=(C\oplus ...
-2
votes
1answer
265 views

Show that the following tautology is a theorem of natural deduction

I'm struggling to apply the theorems of natural deduction to these two examples. $$((p \to q) \land (p \to \neg q)) \to \neg p$$ $$((p \to q) \land (p \to r)) \to (p \to (q \land r))$$ Can anyone ...