Questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions would fit very nicely under this tag. Questions about other kind of logics should be tagged with [logic] instead.

learn more… | top users | synonyms (1)

0
votes
0answers
19 views

Weighted partial MaxSAT (and MinSAT) with real-valued weights?

Consider the following optimization problem ($\min$-version also of interest): $$ \max_{β\in\{0,1\}^m}\{c'φ(β): ψ(β)=1\} = \max_{\phi\in\{0,1\}^n}\{c'\phi: β\in\{0,1\}^m, \phi=φ(β), ψ(β)=1\},$$ ...
0
votes
1answer
35 views

Propositional logic formula checking

I'm answering a question about propositional logic formulas, and was hoping one of you guys could check over my answer. "Either the lift doors are open or the lift is moving and lift doors are ...
1
vote
2answers
76 views

position of atomic propositons in bi-conditionals

In implication position of $p$ and $q$ is important and can't be interchanged but I guess in case of bi-conditionals these two can be interchanged freely. I mean to say $p\to q$ and $q\to p$ will not ...
1
vote
5answers
101 views

Verify that $\bigl(p\to(q\to r)\bigr)\to \bigl((p\to q)\to (p\to r)\bigr)$ is a tautology.

Verify that $\bigl(p\to(q\to r)\bigr)\to \bigl((p\to q)\to (p\to r)\bigr)$ is a tautology. I am confused on this whole tautology even after looking at examples both in my book and on-line. I ...
1
vote
1answer
65 views

Defining what a proposition is is in propositional logic

What is an exact definition of a proposition that we can use to apply to sentences in natural language? Are the following propositions? 1.) "I am calling you a liar." 2.) "4 is the square root of ...
7
votes
3answers
144 views

How or why does intutionistic logic proof negations from within the theory, constructively?

I'm having a little of a cognitive dissonance why, in intuitionistic logic, it's possible to show stentences like $(\neg A \land \neg B) \implies \neg(A\lor B).$ In plain text: If 'A isn't true' as ...
1
vote
6answers
100 views

Basic Tautology Question

I'm reviewing an old exam to study for my upcoming final, and one of the questions is this: "Show that $a∨b \rightarrow¬a \rightarrow b$ is a tautology" My professor gave us this definition for ...
0
votes
1answer
33 views

Nested Quantifiers - Differentiating between $\forall x \forall y$, $\forall x \exists y$, and $\exists x \exists y$

I have a few questions regarding quantifiers which I'm still not clear about. 1) $\forall x \forall y (x^2 + y^2 = 9)$ I believe this is false as x and y could be 2 and results in 8. 2) $\forall x ...
1
vote
1answer
59 views

Find formulas for the statements

The task is: solve the following problems and justify your answers. ...
0
votes
1answer
60 views

Truth table to prove statements

A, B and C. When questioned A says ''If B did not do it, then it was C." B says ''A and C did it together or C did it alone". C says ''We all did it together." How would i be able to put these into ...
3
votes
1answer
56 views

Proving formula's tautology

Prove that a formula that consists only of logical equality, logical negation and has even number of propositional variables and logical negations must be tautological. I tried it out with couple of ...
0
votes
1answer
29 views

Write $p \rightarrow \lnot q$ in CNF form with only and ,or and brackets

Write $p \rightarrow \lnot q$ in CNF form with only and, or, and/or brackets How on earth would I even do this? Completely lost! Any help appreciated.
0
votes
2answers
73 views

Why is … $A \lor ( \neg A \land B)$ … not … $A \lor ( A \lor\lnot B)\,?$

I have this expression: $$A \lor ( \neg A \land B)$$ So I transformed it to: $$ A \lor ( A \lor \neg B)$$ But my expression table says that I'm wrong! Why?
1
vote
0answers
23 views

Finding DNF for the given problem (Logic)

I'm struggling to find DNF for the given problem: Whats bugging me, is the last line - I'm seemingly unable to get rid of disjunctions in the first 2nd level parenthesis. Any ideas on what am i ...
1
vote
1answer
49 views

Translating from informal logical notation to formal logical notation

While introducing formal logical notation, the book I'm reading says the following: "$\forall x$ in $D$. $P(x)$" can be written as "$\forall x (x$ in $D \rightarrow P(x)$". "$\exists x$ in ...
0
votes
0answers
52 views

How to write Propositional logic equation

Given $n-1$ teams and $m-1$ days, provide a propositional logic equation to illustrate the following: each team can only play 1 home game per day. All possible permutations must be played. I'm not ...
2
votes
1answer
59 views

Help understand “unless”

The statement "r unless s" is defined as "if $\sim s$ then $r$." Now, I can proceed as follows: $$\sim s \rightarrow r $$ $$\equiv \; \sim (\sim s) \vee r$$ $$\equiv \; s \vee r$$ Which means ...
1
vote
1answer
46 views

Prove or refute: $A_1,\ldots,A_n\vdash_{CPL} B \iff (A_1 \wedge \ldots \wedge A_n)\vdash_{CPL} B$

Need to prove or refute: $A_1, \ldots, A_n \vdash_{\rm CPL} B \iff A_1 \land\dots\land A_n \vdash_{\rm CPL} B$ Since we have $\iff$ operator, we have to deal with to directions. Let's begin from ...
2
votes
2answers
56 views

Prove or refute contingent: If A implies B is contingent, then B is too

The question is: If $A, A \to B$ are contingent, then so is $B$ $A, A \to B$ (implies) is a contingent, but how exactly to show «so is $B$»? If I'm using a truth table, how should I show that ...
0
votes
1answer
46 views

How to give an assignment of boolean values such that this expression is evaluated to true?

Given the expression $E$, is there an assignment of boolean values ($true$ or $false$) that we can give to our variables such that this is evaluated to $true$? $E = (¬x + z + ¬v) · (¬v + w) ·(¬z + ...
3
votes
2answers
39 views

Prove/refute: Every tautology is contingent

I'm asking to prove/refute the following statement: Every tautology is contingent. According to definition of contingent: A statement that is neither self-contradictory nor tautological is ...
2
votes
1answer
142 views

What are some practical applications of mathematical/formal logic to science and humanities? [closed]

I am studying a bit of this and so far it seems that, apart from math and computer science, the discipline of Logic is very self facing, with logicians proving things for other logicians. It left me ...
5
votes
3answers
118 views

Can Peirce's Law be proven without contradiction?

Good evening, I heard the proof by contradiction is required for Peirce's law. AFAIK, truth tables are not related directly to proofs by contradiction, and if of an operation $\text {op}$ we have a ...
2
votes
3answers
110 views

deducing $\lnot B \implies \lnot A$ from $A \implies B$

One way how to prove a statement of the form $A \implies B$ is to presume that $A$ is true and deduce $B$. Lets have $A \implies B$ and lets assume that $\text{not}~B$ is true. $A$ is true or it is ...
0
votes
1answer
80 views

Solving box proofs problem

I'm trying to solve this box-proof puzzle but I don't understand how to complete it as I need to somehow assume $A0$ or $\neg\neg B2$. I've used a truth-table solver to confirm that this is a ...
2
votes
0answers
55 views

Help with propositional logic

Hi all this is for a homework where we just started learning logic and I am not very familiar with propositional logic. So we have two problems: To show a proof of the Sherlock Holmes syllogism ...
4
votes
3answers
135 views

Natural deduction proof of $(\alpha\to\beta)\to(\beta\to\gamma)\to(\alpha\to\gamma)$

My teacher has assigned us this exercise as part of our homework: Give a natural deduction proof of $(\alpha\to\beta)\to(\beta\to\gamma)\to(\alpha\to\gamma)$ Here is an example of natural ...
1
vote
2answers
86 views

Difference between $\models$ and $\Rightarrow$

What is the difference between $\models$ and $\Rightarrow$ in propositional logic?
1
vote
1answer
21 views

Validate or invalidate the propositional argument

Validate or invalidate the following arguments $ p\to t$ $ p \to \lnot r$ $q \to p$ $\lnot t \lor r$ $r \to t$ $\therefore \lnot p \land \lnot q \land (r \iff t) $ I could only see why it is ...
5
votes
1answer
66 views

showing $\neg\alpha\vee\delta,\neg\beta\vee\neg\delta\vdash \neg(\alpha\vee\beta)\vee\delta$ is valid

Given tertium non datur ($\neg\alpha\vee\alpha$) and: \begin{align} \beta&\vdash\alpha\vee\beta\tag{1}\\ \alpha\vee\alpha&\vdash\alpha\tag{2}\\ ...
0
votes
1answer
40 views

Prove or disapprove a propositions

Let p,q and r be three propositions. Prove or disapprove $(p\to q) \land (q \iff r) \land (p \lor \lnot (\lnot q \lor \lnot r) \equiv p \land q \land r$ so, the way i do is LHS = $(\lnot p\lor q) ...
2
votes
2answers
33 views

Set logic to propositional logic

How would you convert set logic to propositional logic? In particular, I'm not sure how to handle converting $\subseteq$ For example: $$A-(\bar{B} \cup \bar{C}) \subseteq B \cap C$$ My attempt at ...
1
vote
1answer
180 views

Tracing a most-general unifier algorithm

I'm trying to trace the algorithm for getting the most general unifier, and I'm a bit confused. Can there be more than one solution? (although the adjective 'most' suggests otherwise) found online: ...
3
votes
1answer
56 views

DPLL Algorithm $ \rightarrow $ Resolution proof $ \rightarrow $ Craig Interpolation

I really need help here for an exam that I got tomorrow .. Let's say I got a bunch of constraints: $ c1 = { \lnot a \lor \lnot b } \\ c2 = { a \lor c } \\ c3 = { b \lor \lnot c } \\ c4 = { \lnot b ...
3
votes
2answers
47 views

Is entailment biconditional or conditional?

When we say a KB entails Q it means that it is never the case that KB is true and Q is false. Does this mean entailment is similar to the conditional statement KB -> Q? I'm confused because our ...
0
votes
0answers
21 views

If reduct of a formula is Tautology, Then there exists no stable models?

The Definition of a Stable model says that if I is a Stable model of F, this should be the only Interpretation that satisfies the Reduct of the Formula F. But for any formula F', If the reduct of F' ...
0
votes
1answer
34 views

Complete recursively Set

The set $\Sigma=\{ p_1\rightarrow p_2, p_2\rightarrow p_3, ... \}$ Is it complete? why? Is it recursively axiomatizable? Why? Is the consequences of this set recursive? Why? Thanks so much.
1
vote
2answers
36 views

I have confusion while translating propostions to logical expressions

I have following propositions: p:Grizzly bears have been seen in the area. q:Hiking is safe on the trail. ...
2
votes
1answer
159 views

Tautological and logical consequence

In Enderton's book on Logic, it is mentioned that Pc is not a tautological consequence of AxPx (when both are taken as sentence variables for propositional calculus) but Pc is a logical consequence of ...
0
votes
2answers
57 views

What is a Sub Formula and What is a Maximal Sub Formula in Propositional Logic

What is a Sub formula of a Propositional Formula? Suppose I have a formula C or -C Then what are the sub formulas of this and what is the maximal sub formula of this Propositional Formula. I am a bit ...
3
votes
1answer
129 views

Axioms based on $\leftrightarrow, \lor, \bot$ for propositional intuitionistic logic?

Propositional intuitionistic logic can be axiomatized based on $\;\to, \land, \lor, \bot\;$, with modus ponens $$ \text{from }\; \phi \;\text{ and }\; \phi \to \psi \;\text{ infer }\; \psi $$ as the ...
2
votes
1answer
87 views

tautologies and contradictions with $r$

I'm really struggling to understand tautologies and contradictions. I've been able to do $(p \rightarrow q) \leftrightarrow (\lnot q \rightarrow \lnot p)$ and I understand why it is a tautology, ...
3
votes
8answers
620 views

How do I prove this statement is tautology without using truth tables?

How do I prove the following statement is a tautology, without using truth tables? $$[¬P ∧ (P ∨ Q)] → Q$$ I know that if we assume $Q ≡ T$ then no matter what the truth value of what is to the left ...
0
votes
1answer
98 views

Propositional Logic questions about tableau method

Hello i am learning for my exam from logic, I came across the question which i don't know how to solve it. Can tableau for a propositional formula containing an infinite path exist? Can be tableau ...
3
votes
2answers
46 views

Test the validity of the arguments

1) "If interest rates are low, then housing starts are up. If housing starts are up, then marriage rates are high. If interest rates are low, then the economy is good. The economy is not good. ...
1
vote
0answers
63 views

Propositional logic question for designing new proof system

Try to solve question from Logic in Computer Science 2nd by Huth & Ryan Natural deduction is not the only possible formal framework for proofs in propositional logic. As an abbreviation, we ...
3
votes
1answer
124 views

Soundness of a rule of a proof system with respect to the truth tables?

I have the following question: "Explain the concept of the soundness of a rule of a proof system with respect to the truth tables" Would it be correct to state the following: "A rule of a proof ...
3
votes
2answers
107 views

is $p \land (p \lor q)$ a tautology?

I would just like to know whether my work is correct before I continue on with the rest of the questions. $$p \land (p \lor q)$$ $$p \land (\lnot p \rightarrow q)$$ $$(p \land \lnot p) \rightarrow ...
1
vote
0answers
32 views

Deriving ¬R from {R↔(R∨(P∧¬P)),R↔¬P,¬P→(P↔(Q→Q)),P→Q} [duplicate]

Give a derivation of $\neg R$ from the following premises: $$\{R\leftrightarrow(R\lor(P\land \neg P)), R\leftrightarrow\neg P, \neg P\to(P\leftrightarrow(Q\to Q)), P\to Q\}$$ using the ...
1
vote
2answers
80 views

Deriving $\neg R$ from $\{R↔(R∨(P∧¬P)), R↔¬P, ¬P→(P↔(Q→Q)), P→Q\}$

Give a derivation of $\neg R$ from the following premises: $$\{R\leftrightarrow(R\lor(P\land \neg P)), R\leftrightarrow\neg P, \neg P\to(P\leftrightarrow(Q\to Q)), P\to Q\}$$ using the ...