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)

5
votes
1answer
58 views

Propositional Logic: Proof involving only the symbols $\{\rightarrow,F \}$

I feel like I literally tried everything. I'm exhausted, and could really use some help. I was instructed to prove some logic proposition using only the symbols $\{\rightarrow,F \}$. Let me first ...
0
votes
2answers
2k views

How can I prove [P->(Q->R)] is equivalent to [(P^Q) ->R]

I'm a freshman CS student at my university and i'm struggling with understanding my professor through his thick accent. I've asked him to explain the proof for this multiple times and still have ...
2
votes
1answer
41 views

Satisfiability proof of formulas with pure literals

Let $\varphi$ be any propositional formula in negation normal form (NNF). A literal $\ell$ is pure in a formula $\varphi$, if the complement of $\ell$, $\ell^c$, does not occur in $\varphi$, where ...
3
votes
1answer
123 views

Proving that a propositional theory of any cardinality has an independent set of axioms

This is exercise 1.2.19 from Chang & Keisler's Model Theory, which has been giving me a headache for some time now. Let $\mathscr{S}$ be a given propositional language of any cardinality (i.e. ...
3
votes
1answer
35 views

Prove that ≿ is transitive iff ≻ and ∼ are transitive

Let ≿ be a complete preference relation (as in game theory). How to prove that ≿ is transitive if and only if ≻ and ∼ are both transitive? My reasoning is as follows. ...
-1
votes
2answers
73 views

Simplifying on logic Operations

I need simplify the following proposition to 2 logic operations using the laws of the algebra of propositions. Write each step on a separate line with the algebra law you used as a justification. ...
0
votes
1answer
39 views

I am trying to use proof of sequence correctly to make valid

Here I am trying to use a proof sequence so that the argument is valid (hint: the last A’ has to be inferred). (A → C) ∧ (C → B') ∧ B → A' Here are my steps I tried but not sure if this is correct ...
7
votes
6answers
1k views

How to demystify the axioms of propositional logic?

How might I go about getting some intuition on the typical axiom schemes given for propositional logic? They seem rather mysterious at first glance. For example, these are taken from: ...
1
vote
1answer
34 views

How to evaluate the single turnstile symbol ($\vdash$) in propositional logic?

Wikipedia says, that: $x \vdash y$ means y is provable from x (in some specified formal system). But what do you actually check or calculate, when you have $(a \land \lnot b) \vdash a$? Has $(a ...
0
votes
1answer
44 views

Rewrite predicate formulas in propositional calculus

Suppose that the universe of discourse of the atomic formula P(x,y) is the set {0,1,2,3,4,5}. Write each of the following propositions using dis-junctions, conjunctions and only one negation: 1) ∃x ...
0
votes
0answers
46 views

Trying to justify each step correctly in proof sequence

I am trying Justify each step in the proof sequence below for correctly with [A → (B ∨ C)] ∧ B' ∧ C' → A' So I justified my steps here but I am not sure at 1 to 3 if I did it correctly. A → (B ∨ ...
1
vote
1answer
36 views

Prove that a boolean function using only $\vee$ and $\wedge$ must attain the value $1$ at least once

Please give me feedback on this Prove that a boolean function constructed only by using $\vee$ and $\wedge$ (without using $\sim$ ) must attain the value $1$ at least once.
0
votes
0answers
28 views

Two easy questions of propositional logic [closed]

if $ M_1\vee M_2$ is unsatisfiable can we say $M_1 \models\neg M_2?$ if $M\models\psi$ then does$\neg\psi\models \neg Μ?$
0
votes
0answers
34 views

Non Satisfiability of disjuction

Problem: If S1,S2 are (possibly infinite) sets of propositional formulas where their union: S1VS2 is not satisfiable, prove that there exists an ψ such that S1|=ψ and S2|=¬ψ. Can we say that if ...
0
votes
1answer
468 views

Propositional Logic “Riddle/Puzzle”

I have this kind of 'riddle' as a question that i need to complete, however I'm not sure what to do of it. This is the question: ...
2
votes
1answer
48 views

Proving $(p\to q)\land(p\to r) \equiv p\to(q\land r)$ using logic laws — short cut or incorrect?

Working through this problem: Using logic laws, show that the following are logically equivalent: $$(p\to q)\land(p\to r)\qquad\text{and}\qquad p\to(q\land r).$$ The way I did the problem is ...
0
votes
1answer
36 views

Exam preparation: logic - problems on (maximally) consistent sets

I am preparing for an exam on aspects of Logic related to propositional and first order logic. One of my revision exam questions is . I have attempted this question but I am really struggling with ...
0
votes
2answers
81 views

Why $ M\models \forall x ( \alpha \to \beta)$ Is False? [closed]

if M be a model and $\alpha$ and $ \beta$ be two formula the following is False: $ M \models \forall x ( \alpha \to \beta)$ if and only if $ M \models \forall x \alpha$ has conclusion $ M \models ...
1
vote
1answer
52 views

Can't get Logical Error

Firstly I 'll mention Absorption laws : $((\sim p) \vee q) \wedge (\sim q)=(\sim p)$ $((\sim p) \vee q) \wedge p=q$ Also, $p \Longrightarrow q = (\sim p) \vee q$ And, $p \Longleftrightarrow q = ...
1
vote
1answer
44 views

If there are Predicates before Predicate Calculus, why is it called such?

In my understanding, predicates are synonyms of relations: mappings of an ordered set (a,b) to the set of values "True" and "False" Well, propositional calculus comes before predicate calculus, and ...
0
votes
1answer
49 views

Proving these are logically equivalent?

How to prove that these are logically equivalent using laws? a. $p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)$ I used the Conditional law and DeMorgan's Law and eventually arrived at $-(p ∨ q) ∧ -(p ∨ q)$ but ...
0
votes
0answers
41 views

Proof by contradiction that $P \rightarrow Q$ is true

Let $\tau$ be a closed tableau. Prove that $\tau$ is not satisfiable. So let's say the statement can be expressed by $P \rightarrow Q$. To prove that this statement is true, we look at the assumption ...
1
vote
1answer
53 views

Let $\tau$ be a closed tableau. Prove that $\tau$ is not satisfiable.

Let $\tau$ be a closed tableau. Prove that $\tau$ is not satisfiable. Okay can prove this by contradiction. So we say that a tableau $\tau$ is $\textit{satisfiable}$ iff there exists an ...
3
votes
2answers
73 views

If it rains, John is sick. It didn't rain. $\vdash$ John wasn't sick. Is this valid?

If it rains, John is sick. It didn't rain. $\vdash$ John wasn't sick. I would say that this is false since the weather isn't directly influencing John's health. Am I right or wrong? Should I use ...
2
votes
1answer
74 views

What is the _simplest_ way to solve problems of this kind?

Two doors with talking doorknockers - one always tells the truth and one always lies. One door leads to death other to escape. Only one question may be asked to either of the door knockers. What would ...
0
votes
1answer
23 views

Logical Equivalence of Wffs in Sentence, Predicate Logic using Tables, Interpretations Resp.

just curious if there is a formal name for the results that: a) Two wffs in Sentence Logic are equivalent iff their truth tables are equal , as binary functions of {T,F} b) Two wffs A,B in ...
4
votes
9answers
200 views

Why is the negation of $A \Rightarrow B$ not $A \Rightarrow \lnot B$?

The book I am reading says that the negation of "$A$ implies $B$" is "$A$ does not necessarily imply $B$" and not "$A$ implies not $B$". I understand the distinction between the two cases but why is ...
2
votes
3answers
71 views

What is the negation of the statement “Every odd nmber is divisible by 2”.

Intuitively,I think it is "no odd number is divisible by 2" or it could be "every odd number is not divisible by 2". Is this a trivial question or is there more to it? What is the correct answer? BTW ...
2
votes
1answer
67 views

RAA elimination and inference a theory ?!

Can somebody explain the why if we eliminate RAA rule in natural deduction system on propositional logic, why ~$(p \wedge $~$p)$ is not inference from the ...
1
vote
1answer
81 views

direct hint to showing a formula is valid?

we know A formula is logically valid (or simply valid) if it is true in every interpretation. These formulas play a role similar to tautologies in propositional logic. which one could direct me to ...
2
votes
2answers
62 views

Is this truth table correct?

Is this truth table correct? Sorry for the formatting Truth table for $p ∧ c$ and $p ∨ c$, with $c$ representing a contradiction: $$\begin{array}{cc|cc} p & c & p∧c&p∨c \\ \hline T ...
2
votes
2answers
2k views

Tautology Proof without truth table

How would I go about proving this without a truth table? $[(p \lor q) \implies r ] \implies [ \neg r \implies (\neg p \land \neg q)]$
0
votes
1answer
55 views

Let $\tau$ and $\rho$ be tableaus such that $\tau \leadsto \rho$. Prove that $\tau$ is satisfiable if and only if $\rho$ is satisfiable.

I have this definition: Let $\nu$ be any propositional interpretation. Let $b$ be any branch of a tableau. Say that $\nu$ is faithful to b if and only if for every formula, $A$, on the branch, ...
4
votes
1answer
51 views

Show $\models(\phi\rightarrow(\psi\rightarrow\theta))\rightarrow((\phi\rightarrow\psi)\rightarrow(\phi\rightarrow\theta))$

Question: Show $\models(\phi\rightarrow(\psi\rightarrow\theta))\rightarrow((\phi\rightarrow\psi)\rightarrow(\phi\rightarrow\theta))$ Answer: (1) Let, ...
0
votes
1answer
43 views

how we can prove that argument $P_1,P_2,…,P_n $?

I ran into a one claims on LOGIC. how can add more direction or hint to me? if we have an argument $P_1,P_2,...,P_n $ such that $ n>3$ ($p_i$ is premise) why $P_1,P_2,....,P_n,P_1$ is ...
1
vote
0answers
37 views

How we can prove that the logical result of a set is effectively enumerable? [duplicate]

How we can prove that the logical result of $\{(p_i \vee $~ $p_{i+1}$$) $$: i \in \mathbb{N} \}$ is effectively enumerable ? Update: as one user requests, I add my method. I use truth table for ...
0
votes
1answer
40 views

Proving tautology without using truth tables

I have a statement (P∧Q∧(R∧P⇒~Q))⇒~R that I need to prove tautology without using truth tables. I understand I'll be using inference rules. Here's what I've tried ...
1
vote
2answers
35 views

Maximal consistency proof for set of propositional logic with specific restriction?

I ran into struggle when I comes to one sentence on logic. Why the set of all propositional that under any valuation has value 1 is not maximal consistent ? ...
0
votes
0answers
46 views

Interpretation and truth table is enough to showing validity or a better way?

I'm so glad that find this useful site. anyway, I ran into some challenging ways to find a formula is valid. Here is two example in my note that called valid. I ran into such a problem with making ...
0
votes
2answers
42 views

Valid Formula in First Order Logic

I am a little confused about the validity of first order logic formulas. How we can using formal notation to prove the following is VALID? $ \exists x \exists ...
0
votes
3answers
80 views

'If…then…' and '…if…' and '…only if…' and 'If… only then…' statements?

Suppose you have two statements A and B and "If A then B". I am trying to think of what this implies and alternative ways of writing this. I think "If A then B" = A$\rightarrow$B = "A is ...
1
vote
1answer
435 views

proof of validity of tautology in first order logic

Every first-order logic formula which has a tautological shape in propositional logic is a valid formula. Will it be possible to give a formal proof for the above ? Thanks and Regards.
0
votes
0answers
32 views

Formalize “Statement $A$ is the correct explanation of statement $B$”

If I have two statements. Let say Statement $A$ and Statement $B$. What will be the necessary condition or how to write the following conditions mathematically? Statement $A$ is the correct ...
9
votes
9answers
1k views

I can't understand logical implication

I just started studying logic (high school) anyway...for the truth table of logical implication If sentence $A$ is true and $B$ is true then $A\implies B$ is true. does that mean if $A$ and $B$ are ...
1
vote
1answer
41 views

Why if the antecedent P is false, and the consequence Q true, then the implication P $\Rightarrow$ Q is true? [duplicate]

I know that that's the definition but I wonder why logicians choose that thefinition to be true. It sounds strange to me and I cant make sense of it if someone tell me 'if the sky is red, then I'm ...
1
vote
1answer
63 views

What is the difference between Boolean logic and propositional logic?

As far as I can see, they only employ different symbols but they operate in the same way. Am I missing something? I wanted to write "Boolean logic" in the tag box but a message came up saying that if ...
-3
votes
1answer
31 views

Can boolean logic compute any sort of mathematical operation?

Computers fundamentally do logical operations on the input and memory they have (as far as I know). Computers are used by mathematicians to do all sorts of mathsy operations (as far as I know). Does ...
1
vote
1answer
40 views

Showing $(¬P\wedge¬Q)\vee(¬P\wedge Q)\equiv¬P\wedge(¬Q\vee Q)$ by distributive law(s)

I want to show that $$(¬P\wedge¬Q)\vee(¬P\wedge Q)\equiv¬P\wedge(¬Q\vee Q)$$ by one of the two Distributivity Laws: $$P\wedge(Q\vee R)\equiv(P\wedge Q)\vee(P\wedge R)$$ $$P\vee(Q\wedge R)\equiv(P\vee ...
7
votes
4answers
177 views

Showing $(P\to Q)\land (Q\to R)\equiv (P\to R)\land[(P\leftrightarrow Q)\lor (R\leftrightarrow Q)]$ {without truth table}

Problem: Show $(P\to Q)\land (Q\to R)\equiv (P\to R)\land[(P\leftrightarrow Q)\lor (R\leftrightarrow Q)]$ Source: As was noted in the original post, this problem is from Daniel J. Velleman's book ...
0
votes
1answer
39 views

Why is that: $P \Rightarrow T$, truth value(P) = ?, but $(P\Rightarrow F) \Rightarrow$ Truth value (P) = F

Why is that: If: P :proposition. T: true statement F: false statement $$P \Rightarrow T $$ In this statement, we can not have for sure the Truth value of P (if P is T or F) , but, in this ...