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
1answer
57 views

Cardinality of Distinct Hilbert Systems with Detachment

Let us consider all formulas T of classical propositional logic which are tautologies up to simple substitution of variables where a variable can get simply substituted for another variable if and ...
1
vote
1answer
351 views

Propositional Logic and First-Order Logic

I am having a hard time distinguishing between the two different logics. If we consider the statement, “Squares adjacent to the Wumpus are smelly,” and are asked to express it as First-Order Logic, ...
4
votes
1answer
98 views

Some doubts about interpretation of an atomic formula in predicate calculus

I have some doubt related to the interpretation of atomics formulas in predicate calculus. In predicate calculus a formula will be interpreted on a specific domain that is where I take the allowed ...
6
votes
3answers
151 views

Equivalence relation using tableaux

How can I prove that two formulae are equivalent using analytic tableaux? For example, how can I prove the following theorem? $$ (p \rightarrow q) \equiv (\neg q \rightarrow \neg p)$$
0
votes
1answer
106 views

Some doubts about predicate calculus

I am studying the predicate calculus in First Order Logic and I have some doubt about this argument. In my book I find that a formula in the predicate calculus is built from Literals constructed ...
3
votes
0answers
148 views

meaning of ``partial converse''

In the definition of a commutative ring $(R,+,\times)$, one of the postulates given is that of uniqueness, i.e. that $$ a=a', b=b'\implies a+b=a'+b', ab=a' b'.$$ The text states that for the system ...
1
vote
1answer
74 views

Predicate equivalence from Horn clauses?

I have the following Horn clauses (=P): even(n). forall X (even(s(s(X))) <- even(X)). even'(n). forall X (even'(s(s(X)) <- even'(X)). Can I prove one ...
1
vote
3answers
637 views

About NOT elimination/introduction and RAA rules on Natural Deduction

Can somebody explain the $\neg$-elimination rule in natural deduction?. Searching on books and the web, I found different definitions for it. For example, in my logic I course, the rule is: $A, ...
3
votes
3answers
275 views

Proof of $A \lor B, \lnot A\models B$ with natural deduction

Prove that: $A \lor B, \lnot A\models B$ Looks easy but im stuck, and i dont know if to start with an OR elimination or with NOT introduction. Also, different books/texts/etc about Natural ...
2
votes
2answers
979 views

How to apply De Morgan's law?

If for De Morgan's Laws $$( xy'+yz')' = (x'+y)(y'+z)$$ Then what if I add more terms to the expression ... $$(ab'+ac+a'c')' = (a'+b)(a'+c')(a+c)?$$
2
votes
1answer
356 views

“Rules of inference” when the last premise is a conditional?

Another very basic Discrete Mathematics homework problem. I don't want the answer as much as I want to understand the question: Problem 7 For each of the following sets of premises, ...
3
votes
2answers
287 views

Prove p from ¬¬p

I'm stuck on question 2 of these lecture notes on propositional logic: "2. Propositional Proof. Give a formal proof of the sentence p from the single premise ¬¬p using only Modus Ponens and the ...
3
votes
2answers
102 views

Representing $A \rightarrow B$ as $A \supseteq B$ [duplicate]

I know that many people like to think of elementary logic in terms of Venn diagrams, i.e., elementary set theory. I have never found this representation useful, because I can never remember whether ...
2
votes
2answers
380 views

Some doubts about the differences between logic implication and inference rule

I am studying for an Artificial Inteligence university exam that includes a section dedicated to mathematical logic. I am finding some difficulty in understanding the difference between logical ...
3
votes
4answers
222 views

Proving $q\Rightarrow r \models (p\land q) \Rightarrow (p \land r)$ using only natural deduction.

I'm trying to prove $$q\Rightarrow r \models (p\land q) \Rightarrow (p \land r)$$ using only the natural deduction rules in this handout. Any hints? I am not allowed to do transformational stuff, ...
0
votes
1answer
35 views

Definition by Recursion and a Question about Induction

I have some questions to ask. Suppose I want to define some sequence of propositional formulas $\{\varphi_{j}\}_{j\in\mathbb{N}}$. First, I define it this way. Fix an enumeration ...
1
vote
1answer
150 views

What law of algebra of proposition is happening here?

I'm preparing for a test tomorrow and going over some reading material, and I came across this problem that was worked out. So far I think I'm following each step of logic, but I've hit a wall with ...
3
votes
2answers
682 views

Proof using natural deduction

Prove that $$\lnot r\Rightarrow \lnot p,\lnot(q\lor r),s\Rightarrow(p\lor q)\models\lnot s $$ I'm completely stuck on this one. Only natural deduction inference rules can be used, no de morgan's law ...
2
votes
3answers
127 views

Proving $(A \land B) \to C$ and $A \to (B \to C)$ are equivalent

Prove that $(A \land B) \rightarrow C$ is equivalent to $A \rightarrow (B \rightarrow C)$ in two ways: by semantics and syntax. Can somebody give hints or answer to solve it?
2
votes
2answers
2k views

De Morgan's laws in natural deduction?

We are asked to use natural deduction to prove some stuff. Problem is, without De Morgan's law, which I think belongs in transformational proof, lots of things seem difficult to prove. Would using de ...
4
votes
3answers
106 views

Trying to understand implication

I'm currently slogging through propositional calculus and making my brain do impressions of a pretzel, but I'm slowly getting it though I'd like to see if that's actually true for the problem below. ...
3
votes
2answers
130 views

Definability of Sets of Truth Assignments

I have some questions about under what conditions a set of truth assignments is the model of some set of sentences. To be more precise, suppose I'm dealing with only propositional logic. Let $K$ be a ...
1
vote
1answer
38 views

Is there some sort of function transformation expressing $(X\implies Y)\Leftrightarrow (\neg X\lor Y)$?

Is there a functional interpretation if the replacement for for the material implication?: $$(X\implies Y)\Leftrightarrow (\neg X\lor Y)$$ Given a function from type $X$ to type $Y$, viewed as a ...
5
votes
2answers
178 views

Which law of logical equivalence says $P\Leftrightarrow Q ≡ (P\lor Q) \Rightarrow(P\land Q)$

I'm going through the exercises in the book Discrete Mathematics with Applications. I'm asked to show that two circuits are equivalent by converting them to boolean expressions and using the laws in ...
0
votes
1answer
352 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: ...
1
vote
1answer
96 views

What does $\vdash s \rightarrow (\neg s\rightarrow t)$ mean?

What does this statement mean $\vdash s \rightarrow (\neg s\rightarrow t)$? And how can I prove it?
0
votes
2answers
1k views

what is the diffrence between a term , constant and variable in first order logic languages ?

in the text , the author says that the language contains parenthises , sentintial connectives and n-place functions , n-place predicates , equality sign = , terms , constans and variables i have two ...
-2
votes
2answers
468 views

How to prove that a set of connectives aren't adequate

I guess we have to prove it somehow by an induction as I saw a few examples online. But it just makes absolutely no sense to me... Can somebody explain it in human language? Thank you very much.
0
votes
1answer
551 views

if $p\implies q$ is the same as $\lnot p \lor q$, then…

If $p\implies q$ is the same as $\lnot p \lor q$, then what is $p\implies \lnot q$? I'm not sure if this is $\lnot p \lor \lnot q$, or $\lnot p \lor q$. I'm trying to figure this out, because i have ...
0
votes
2answers
69 views

Regularity of balanced binary strings

How can one tell which number of propositional variables is necessary to express a Boolean function given as a sequence of 0s and 1s (a binary string) of length $2^n$ as a Boolean formula? ...
1
vote
1answer
44 views

Appearance of sentence parameters in a theorem

Is it true that if $A$ is a formula in a Hilbert system $H$, then if $B_1,B_2,\ldots,B_n$ is a proof of $A$ in $H$, any sentence parameter not appearing in $A$ doesn't appear in $B_1,\ldots,B_n$? If ...
2
votes
2answers
1k views

Is there a difference between 'inconsistent', 'contrary', and 'contradictory'

Is there a difference between 'inconsistent' 'contrary' and 'contradictory'? As far as I understand, two statements are inconsistent when they can not both be true; two statements are contradictory ...
1
vote
1answer
104 views

Implication: F $\implies$ T

Why is F $\implies$ T taken as true? Why is this the "convention"?
3
votes
0answers
59 views

Boolean combinatorics

Every finite Boolean algebra has a "middle layer", corresponding to the subsets of size $n/2$ (when looking at the algebra of subsets of $[n]$) or to a set of formulas including $p_i, \neg p_i, p_i ...
5
votes
2answers
667 views

Deriving A implies B from Not A

My logic textbook has the following example showing how to derive $A \to B$ from $\neg A$: First we assume $A$ and use the conjunction introduction rule which results in a contradiction $[A] \land ...
1
vote
2answers
157 views

Do the premises logically imply the conclusion?

$$b\rightarrow a,\lnot c\rightarrow\lnot a\models\lnot(b\land \lnot c)$$ I have generated an 8 row truth table, separating it into $b\rightarrow a$, $\lnot c\rightarrow\lnot a$ and $\lnot ...
1
vote
4answers
140 views

Writing an expression using logic

Write an expression using letters $\land, \lor, and$ $\neg$ which has the following truth table: $$\begin{array}{ccc|c} P&Q&R&???\\ \hline T&T&T&F\\ T&T&F&T\\ ...
0
votes
3answers
86 views

what is the relation between not A and everything but A

I am examining Bayes' Theorem, and wondering about the alternative interpretations of ~A, as being: not A, ¬ A everything but A, ∀-A And how this will affect the use of probabilities. ...
2
votes
2answers
91 views

Are these propositions equivalent?

Statement 1: Maria will find job if she learns mathematics. Statement 2: Maria will find a job unless she does not learn mathematics. I know the answer is probably that these are same, but ...
3
votes
1answer
103 views

Boolean Algebra Transform

I am revisiting Boolean algebra after a long while. Can somebody help show me how to simplify the LHS to get the RHS? $$abc * a'bc + (abc)' * (a'bc)'\quad = \quad \;b'+c'$$
2
votes
3answers
155 views

Logic Negation Symbols

$\def\nn{\mathord{\sim}}$ This is a rather simple question but I can't find an exact answer on it. In examples, I've seen $\nn$ and $\lnot$. These fall under ‘negation’. If they both fall under ...
1
vote
1answer
85 views

Simple logic equivalence incorrect

I am having some problems negating a rather simple logical statement. I am currently taking a introduction course, so please bear with me if my question is silly. I am supposed to turn this: $$ ...
1
vote
1answer
100 views

Logical correlation from Oedipus myth

My girlfriend likes the myths and she found an MIT article about Oedipus myth which is looks interesting for her. She showed me, but for me it is looks like no correlation between the logical ...
2
votes
2answers
1k views

Every sentence in propositional logic can be written in Conjunctive Normal Form

While reading through Artificial Intelligence: A Modern Approach by Stuart Russell and Peter Norvig, I came upon the following question: Any propositional logic sentence is logically equivalent to ...
1
vote
1answer
82 views

In Fitch, is a symbol not in a specified language automatically free?

In Fitch proofs where no language has been specified, we (at least seem to) treat lines that have the form $$p(x)$$ to mean that $x$ "can be anything". That is they are equivalent to $$\forall ...
6
votes
1answer
255 views

distribution of categorical product (conjunction) over coproduct (disjunction)

In the classical and intuitionistic propositional calculi, it is straightforward, using natural deduction, to derive $((A \land C) \lor (B \land C))$ from $(A \lor B) \land C$: Assume $(A \lor B) ...
1
vote
2answers
1k views

Prove logical equivalence

\begin{gather} (p \to q) \equiv (\lnot p \lor q) \\ \lnot(p \land q) \equiv (\lnot p \lor \lnot q) \end{gather} Can these be proven without truth tables?
1
vote
1answer
54 views

Less absorption in Minimal Logic?

I just wonder whether the following is not derivable in Minimal Logic: $$ \bot \dashv\vdash \bot \land A \hspace{3em}\mbox{/* not derivable */ }$$ I read this that although Minimal Logic attaches ...
2
votes
3answers
291 views

Use rules of inference to show

Premises: $p \land \lnot s$ $q \to (r \to s)$ Conclusion: $(p \to q) \to \lnot r$ Use rules of inference to show the above argument is valid. I only manage to get $(p \to q) \to (p \land ...
2
votes
1answer
75 views

Equivalence of two very specific propositional calculi

Let $H$ and $L$ be two propositional calculi. $H$ has as inference rule modus ponens only, and three axiom schemes: P1: $A\rightarrow . B\rightarrow A$ P2: $(A\rightarrow . B\rightarrow ...