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)

2
votes
1answer
67 views

Are my answers for these propositional calculus questions right?

Formalize the following English sentences as propositional logic formulas: $i)\quad$ "When the front and back doors are closed then the light is off." $ii)\quad$ "Either the lift doors are open or ...
0
votes
2answers
73 views

Where do the brackets go in $p \wedge q \vee \neg p \rightarrow \neg q$?

I have been give the following question for homework: Let $p$ be the statement "She will graduate" and let $q$ be "She will find a job". Then what would be: "Either she will graduate and find ...
1
vote
0answers
75 views

Propositional logic truth tables

For the exam that I am taking, propositional always comes up with identical questions. These include writing a sentences in propositional logic, which I can do. But also drawing a truth table for ...
4
votes
5answers
150 views

Are $p \to (q \to r)$ and $p \to (q \wedge r)$ logically equivalent?

Is $p \to (q \to r)$ logically equivalent to $p \to (q \wedge r)$? I simplified each one, I got $\neg\, p \vee(q \vee r)$ and $\neg\, p ∨(\neg\, q \wedge r)$ respectively. Not sure if my ...
0
votes
1answer
49 views

Does $\neg(x > y)$ imply that $y \geq x$?

Given any arbitrary binary relation $\geq$ defined on some set $S$, we define a new binary relation $>$ on $S$ by: $$ x > y \quad\text{iff}\quad (x \geq y) \wedge \neg(y \geq x) $$ In accordance ...
2
votes
1answer
135 views

How to check the validity of this argument using the rules of inference?

I have this argument : I play basketball and football. If today isn't Saturday, then I play basketball and football. If today is Friday OR today is Saturday, then I don't play football. Therefore, ...
6
votes
2answers
219 views

Is this a valid proposition?

Consider following two sentences. $x^2 = 1.$ Today is Thursday. The first statement can't be a proposition. because the truth of (1) depends on the value of $x$. For some values of $x$ it is true ...
1
vote
1answer
44 views

Mathematical logic question propsitional logic

"When the front and back door are closed then the light is off" p - "front" q - "light is off" r - "back doors are closed" $$(p\land r) \rightarrow q$$ Would this be logically correct?
2
votes
4answers
430 views

Satisfiability Problem: Determining Which People To Invite

When planning a party you want to know whom to invite. Among the people you would like to invite are three touchy friends. You know that if Jasmine attends, she will become unhappy if Samir is ...
4
votes
7answers
219 views

Conditional Statements: “only if”

For some reason, be it some bad habit or something else, I can not understand why the statement "p only if q" would translate into p implies q. For instance, I have the statement "Samir will attend ...
0
votes
1answer
21 views

Are all substitution-closed sets schematic?

I assume everyone is familiar with propositional logic and its language. Let $S$ be a set of wffs of propositional logic. The set $S$ is said to be substitution-closed iff whenever $x$ is in $S$, ...
0
votes
0answers
21 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
37 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
77 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
104 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
75 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
4answers
156 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
119 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
41 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
63 views

Find formulas for the statements

The task is: solve the following problems and justify your answers. ...
0
votes
1answer
66 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
64 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
31 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
78 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
24 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
57 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
60 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
60 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
48 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
65 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
49 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
40 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
165 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
124 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
113 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
98 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
57 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
145 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
24 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
71 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
42 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
38 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
202 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
63 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
57 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
35 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
38 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
194 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 ...