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)

1
vote
1answer
22 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. ...
0
votes
1answer
29 views

Propositional Logic Puzzle - Enderton

This is a question from Enderton. You are in a land inhabited by people who either always tell the truth or always tell falsehoods. You come to a fork in the road and you need to know which ...
0
votes
0answers
46 views

Inference in First Order Logic [closed]

Suppose we have $ E \bigwedge R \Rightarrow B$ $ E \Rightarrow R \bigvee P\bigvee L $ $ K \Rightarrow B$ $ \neg (L \bigwedge B ) $ $ P \Rightarrow \neg K $ which of them cannot inference from ...
2
votes
0answers
37 views

Proposition into spoken language

Given: $\sim( p \leftrightarrow (q \vee r) )$ $p:$ It's raining $q:$ The sun is shining $r:$ There are clouds in the sky. Translate the proposition into spoken language. ...
3
votes
5answers
143 views

Is $'' \sum_{n = 1}^{\infty} (-1)^n \; \text{is a real number}''$ an invalid statement or a false proposition?

So we're beginning an introductory logic course and my professor is giving examples for valid statements/ propositions - meaningful statements that are either true or false but not both. So he puts ...
1
vote
1answer
34 views

Laws of equivalence needed to prove $\;q \leftrightarrow (¬p ∨ ¬q) ≡ (¬p ∧ q)\;?$

I'm not sure which laws should be applied and how I can tell for myself how to discern which laws I should use - any and all help is appreciated.
3
votes
3answers
84 views

If $(A \vee B) \wedge (¬B \vee C)$ is true, then $(A \vee C)$ must be true … can I argue that?

If $(A \vee B) \wedge (¬B \vee C)$ is true, then $(A \vee C)$ must be true ... can I argue that? I don't see how I can argue that $(A \vee C)$ must be true because can't we have $(T \vee T) ...
2
votes
3answers
48 views

Indirect proof , odd and even numbers

"Show by indirect proof that if 5n + 3 is an even number then n is an odd number" How could this be solved? I guess I'm in the right track but I don't know how to conclude.
3
votes
2answers
49 views

How to prove the following using direct proof

$[(\sim p \vee q) \wedge p ] \Rightarrow q $ What should be done next in order to apply direct proof to the example above? The following process has been already done but seemingly it's incorrect: ...
0
votes
1answer
16 views

Conversion of disjunctive normal form to conjunctive normal form

Explain how $ (p \lor q \lor r \lor s) $ can be re-written into an equivalent CNF formula such that each clause contains exactly $3$ variables or negations of variables.
0
votes
2answers
85 views

Understanding logical form of “Nobody in the calculus class is smarter than everybody in the discrete math class”

I'm self studying How to Prove book and have been working out the following problem in which I have to analyze it to logical form: Nobody in the calculus class ...
0
votes
1answer
20 views

Analyzing Logical Forms involving quantifiers

I have been solving the following problem from How to Prove book: Analyze the logical forms of the following statement: Everyone likes Mary, except Mary ...
0
votes
1answer
30 views

Readings on more general/abstract notions of induction related to logic

Can someone suggest references to understand the more general/abstract concept of induction? Specifically, I am trying to justify to myself what is called induction on the "complexity of a ...
1
vote
2answers
51 views

Validity in propositional calculus.

I have read some of the answers on similar questions but I can't really get my head around this. So, here are 2 questions I need to answer. Show using a truth table: That the inference ...
1
vote
1answer
61 views

Thinking logically instead of Venn diagrams

I hit upon the following identity while reading the book How to Prove: $$(A \cup B) \backslash B \subseteq A$$ Now if I solve this logically I can reduce this like this: $$ \begin{gather*} x \in (A ...
0
votes
2answers
37 views

What is the Equivalent formula of $((a\to b) \to ((a \to c) \to (c \to a)))$

Need help to solving a logic. The question is to find an equivalent to the following logic. $((a\to b) \to ((a \to c) \to (c \to a)))$ Thanks in advance for help.
0
votes
3answers
43 views

Find an equivalent to $(p\lor q) \to (p \lor r)$

I need some help regarding solving a logic. The question is to find an equivalent to the following logic. $(p\lor q) \to (p \lor r)$ Thanks in advance for help.
0
votes
2answers
50 views

How to find the equivalent formulas of $\neg ((p\land q) \to (p \land r))$ [closed]

I have following formula: $\neg ((p\land q) \to (p \land r))$ I need to find equivalent formulas of above expression. Thanks in advance for the help.
3
votes
1answer
34 views

Why is the assumption needed in this conditional introduction?

In the first derivation detailed here, why must we include a subderivation with $P$ as an assumption? We can derive $Q$ (4) from $S \land Q$ (2) without the help of $P$ (3); and then since we have ...
6
votes
1answer
63 views

Unique decomposition of wffs when left and right parentheses are indistinguishable

I'm working through Enderton's book A Mathematical Introduction to Logic 2nd Edition for self study. Section 1.3 Exercise 7 Suppose that left and right parentheses are indistinguishable. Thus, ...
0
votes
1answer
21 views

Is my interpretation of these propositional formulas correct?

We define two propositions P and Q as follows. P: Victoria studies hard for the final exam. Q: Victoria desperately wants to ace the final exam. (a) Translate each of the following statements into ...
2
votes
1answer
52 views

Simplifying ambiguous statements

I have been working on the following question from Velleman's How to prove book: Let S stand for the statement “Steve is happy” and G for “George is happy.” What English sentences are ...
3
votes
2answers
37 views

Forming up Complex logical forms from simple one

This is another problem I have been working from Velleman's How to prove book. Let P stand for the statement “I will buy the pants” and S for the statement “I will buy the shirt.” What English ...
0
votes
3answers
49 views

Logical form of Either and Neither: Alice in room

This is one of the problem I have been working: ...
1
vote
2answers
38 views

Method of verifying answers

I have been reading Velleman's How to prove it book and solving problems of the exercise in it. What concerns me is that I cannot verify if actually my solutions are correct. The book has only ...
-2
votes
2answers
72 views

Creating Truth tables [closed]

What is the truth table for the logical expression? $$ (p \land (p \to q) \land r) \to ((p \lor q) \to r) $$ Frankly, I'm lost.
4
votes
11answers
417 views

Propositional logic problem about a conversation of four people who lie or tell the truth

This is obviously elementary but can't figure it out. I am taking a course named Logic and Introduction to Analysis next semester and wanted to do some reading beforehand but to figure out how deep ...
2
votes
1answer
30 views

Does introduction and elimination rule for an operator determine uniquely its truth table?

My question is regarding the inference of a truth table for an operator given how it behaves according to introduction and elimination. This follows from an exercise I read, and it got me thinking if ...
1
vote
1answer
43 views

Conjuctive Normal Form

In Boolean logic, a formula is in conjunctive normal form or clausal normal form if it is a conjunction of clauses, where a clause is a disjunction of literals; otherwise put, it is an AND of ORs. I ...
0
votes
1answer
44 views

Relation between an unsatisfiable set and a tautology

In mathematical logic, satisfiability and validity are elementary concepts of semantics. A formula is satisfiable if it is possible to find an interpretation (model) that makes the formula true. A ...
1
vote
2answers
38 views

Reducing $ab' + cb + ac$ to $ab' + cb$

Boolean expressions $I = ab' + cb + ac$ and $J = ab' + cb$ have the same truth table. Then why expression $I$ can't be reduced to expression $J$?
1
vote
1answer
36 views

How to prove this logical equivalence using different laws?

Prove that $﹁p → (q→r)$ and $q → (p∨r)$ are logically equivalent using different laws. this is my answer: $﹁p → (q→r) = q → (p∨r)$ $(q→r) = ﹁q∨r$ implication equivalence $﹁p → (q→r) = p∨(﹁q∨r)$ ...
4
votes
1answer
109 views

How to prove Post's Theorem by induction?

The proof of post's theorem is given in my textbook in two pages of explanation using a non-induction method. I was told that ,using induction on length of the proof, one can get a simpler and more ...
0
votes
2answers
74 views

Is it always a tautology?

If any two compound propositions $P$ and $Q$ are equivalent, then is the proposition formed from their biconditional $P \leftrightarrow Q$ always a tautology?
1
vote
1answer
34 views

Correctly understanding truth table problem?

I'm typing up a solution set for an "intro to proof" course. One of the problems asks the student to "construct a truth table for $(P \implies Q) \implies (\neg P)$." I interpreted this as requesting ...
3
votes
0answers
38 views

Proving a graph has a property if all finite subgraphs have that property

Given a graph $G=(V,E)$ and an integer $k\in\mathbb N$, we will say that $G$ is $k$-good if: for every division $V=\bigcup_{i\in I} U_i$ such that $i\not=j \Rightarrow U_i\cap U_j =\emptyset$ and ...
1
vote
3answers
81 views

prove validity of following sequent

How to prove validity of following sequent using rules of conjunction, disjunction, implication, negation etc. Premises: $ c \wedge n \Rightarrow t$ , $h \wedge \sim s$, $h \wedge \sim(s\vee c) ...
1
vote
2answers
73 views

How to deal with equivalences in proofs?

There is a part I need clarification on regarding the use of equivalence and its symmetry. From what I understand in regards to symmetry is that: $ (p \equiv q) \equiv (q \equiv p) $. Given p and q ...
0
votes
1answer
42 views

How to prove validity of following sequent [closed]

How to prove validity of following: Premises: $p\rightarrow q$, $s\rightarrow t$, Conclusion: $(p \lor s) \rightarrow (q\land t)$
0
votes
4answers
191 views

Logic Confusing Problem

I Read one logic book, can my two conclusion are true? 1- Suppose for each valuation v, we have such n that can we say we have such n that 2- Suppose for each ...
2
votes
1answer
111 views

About $\Sigma=\{p_2\to p_1, p_3\to p_2,\, \dots\,\}$ . . .

Suppose $$\Sigma=\{p_2\to p_1, p_3\to p_2,\, \dots\,\}.$$ Which of the following is true? Explain your answer. For any $n$, $$\Sigma\cup\{p_n, \neg p_{n+1}\}$$ is complete and ...
-1
votes
1answer
60 views

Quick Truth Table in Logic Problem

Suppose We Have: How can quickly detect how many "1" are in the truth table of above formula? (without drawing Truth Table). i think by using some inference. any idea? we know there are 11 "1"s ...
-1
votes
4answers
112 views

Which of $\varphi$ or $\lnot \varphi$ can be expressed by using only the $\rightarrow$ connective? [closed]

if we have: $$\varphi = \lnot(p\land q\to r) $$ (original screenshot) a) we can write $\varphi$ in equivalence just by using $\to$ connective. b) we can write $\lnot\varphi$ in equivalence ...
1
vote
1answer
33 views

Discrete math and rules of inference

I recently did this rules of inference/logic question and the method I used was different from the textbook so I was wondering if my work was correct?
-1
votes
3answers
44 views

Help with function proof [closed]

I am asked to prove or disprove that if $f:A\rightarrow B$ is a function, then: If $Y\subseteq B$, then $f^{-1}(B\setminus Y) = f^{-1}(B)\setminus f^{-1}(Y)$. I have no idea how to go about doing ...
1
vote
1answer
59 views

Prove A or (A and B) is equivalent to A [duplicate]

Prove $A \lor (A \land B) \Leftrightarrow A$ without using truth table. The proof may involve expanding $B$ into $B \land B$ or possibly $B \lor B$. I am stuck after playing with distributive law ...
0
votes
1answer
45 views

Logic Pure Subset Problem

for example if we define : $$ \$(p,q,r) = (p\to q)\land(\neg p\to r)$$ how we can inference that set $\{\$,\top,\bot\}$ is Full Functional and not any pure subset of this be full functional.
1
vote
3answers
90 views

Can a statement in FOL be equivalent to two separate independent statements?

This may seem like a dumb question, and it certainly seems dumb to me asking it, but I'm running into a contradiction. I'm looking at the problem of finding a statement $\phi$ such that $\psi$ and ...
1
vote
1answer
32 views

From statement to logic

I have a problem with the modelling of the following statement in propositional logic (warning, I translated it from italian): Martha is not a singer, and she doesn't play violin or flute, but not ...
4
votes
3answers
191 views

Simplifying a categorical proof of constructive dilemma

In axiomatic propositional calculus the following axiom schema captures constructive dilemma: $\newcommand{\lif}{\supset} \renewcommand{\land}{\&}$ \begin{equation} (a \lif c) \lif ((b \lif c) ...